Problem:
Alice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each child.Children get jealous of their immediate neighbors, so if two children sit next to each other then the one with the higher rating must get more candies. Alice wants to save money, so she wants to minimize the total number of candies.
Input
The first line of the input is an integer N, the number of children in Alice’s class. Each of the following N lines contains an integer indicates the rating of each child.
Ouput
Output a single line containing the minimum number of candies Alice must give.
Sample Input
3
1
2
2
Sample Ouput
4
Explanation
The number of candies Alice must give are 1, 2 and 1.
Constraints:
N and the rating of each child are no larger than 10^5.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CandiesDemo
{
class Solution
{
static void Main(string[] args)
{
int N = Int32.Parse(Console.ReadLine());
int[] ranks=new int[N] ;
int[] candi = new int[N];
int results = 0;
for (int i = 0; i < N; i++)
{
ranks[i] = Int32.Parse(Console.ReadLine());
candi[i] = 1;
}
bool IsCompleted = false;
while (!IsCompleted)
{
IsCompleted = true;
for (int i = 0; i < N; i++)
{
if (i == 0)
{
if (ranks[0] > ranks[1] && candi[0] <= candi[1])
{
candi[0] = candi[1] + 1;
IsCompleted = false;
}
}
else if (i == N - 1)
{
if (ranks[N - 1] > ranks[N - 2] && candi[N - 1] <= candi[N - 2])
{
candi[N - 1] = candi[N - 2] + 1;
IsCompleted = false;
}
}
else
{
if (ranks[i] > ranks[i - 1] && candi[i] <= candi[i - 1])
{
candi[i] = candi[i - 1] + 1;
IsCompleted = false;
}
else if (ranks[i] > ranks[i + 1] && candi[i] <= candi[i + 1])
{
candi[i] = candi[i + 1] + 1;
IsCompleted = false;
}
}
}
}
for (int i = 0; i < N; i++)
{
results += candi[i];
}
Console.WriteLine(results);
}
}
}
Alice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each child.Children get jealous of their immediate neighbors, so if two children sit next to each other then the one with the higher rating must get more candies. Alice wants to save money, so she wants to minimize the total number of candies.
Input
The first line of the input is an integer N, the number of children in Alice’s class. Each of the following N lines contains an integer indicates the rating of each child.
Ouput
Output a single line containing the minimum number of candies Alice must give.
Sample Input
3
1
2
2
Sample Ouput
4
Explanation
The number of candies Alice must give are 1, 2 and 1.
Constraints:
N and the rating of each child are no larger than 10^5.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CandiesDemo
{
class Solution
{
static void Main(string[] args)
{
int N = Int32.Parse(Console.ReadLine());
int[] ranks=new int[N] ;
int[] candi = new int[N];
int results = 0;
for (int i = 0; i < N; i++)
{
ranks[i] = Int32.Parse(Console.ReadLine());
candi[i] = 1;
}
bool IsCompleted = false;
while (!IsCompleted)
{
IsCompleted = true;
for (int i = 0; i < N; i++)
{
if (i == 0)
{
if (ranks[0] > ranks[1] && candi[0] <= candi[1])
{
candi[0] = candi[1] + 1;
IsCompleted = false;
}
}
else if (i == N - 1)
{
if (ranks[N - 1] > ranks[N - 2] && candi[N - 1] <= candi[N - 2])
{
candi[N - 1] = candi[N - 2] + 1;
IsCompleted = false;
}
}
else
{
if (ranks[i] > ranks[i - 1] && candi[i] <= candi[i - 1])
{
candi[i] = candi[i - 1] + 1;
IsCompleted = false;
}
else if (ranks[i] > ranks[i + 1] && candi[i] <= candi[i + 1])
{
candi[i] = candi[i + 1] + 1;
IsCompleted = false;
}
}
}
}
for (int i = 0; i < N; i++)
{
results += candi[i];
}
Console.WriteLine(results);
}
}
}
No comments:
Post a Comment