爱丽丝是幼儿园的老师。她想给班上的孩子们一些糖果。所有的孩子排成一排，每个孩子都根据自己平时的表现打分。Alice 想给每个孩子至少 1 颗糖果。因为孩子们在某种程度上嫉妒。Alice 必须根据他们对任何相邻 2 个孩子的评分主题给她糖果，如果一个人的评分高于另一个孩子，他/她必须比另一个孩子获得更多的糖果。爱丽丝想省钱，所以她想总共只给糖果。
输入的第一行是一个整数N，即 Alice 班级的孩子数。以下每一N行都包含一个整数，表示每个孩子的评分。
在输出的唯一一行打印一个整数，描述爱丽丝必须提供的最小糖果数量。
3
1
2
2
4
爱丽丝必须给的糖果数量是 1,2 和 1。
N每个孩子的评分不超过10^5。
谁能帮帮我吗？
您可以分两次执行此操作。从每个人都有一颗糖果开始。
第一个循环 i 从 1 到 n-1（从零开始），如果 rating[i] > rating[i-1] then candies[i] = candies[i-1]+1
然后将 i 从 n-2 循环到 0；如果 rating[i] > rating[i+1] 那么 candies[i] = max(candies[i], candies[i+1]+1)
很容易证明这给了你一个有效的糖果分配，因为第二个循环不能破坏第一个循环所修复的任何东西，并且所有可能的评级差异必须被两个循环中的一个捕获。这将使用最少数量的糖果并不明显，但如果您仔细检查每个作业，您可以证明条件证明每个步骤所需的糖果数量（由特定个人）的下限。
To make the analysis of this algorithm more interesting I will the following input:
9
2
3
4
4
4
2
1
3
4
Firstly, notice if a kid sits next to a kid who is getting x candies and that kid has a lower rating then the first kid should get at least x+1 candies. Making the difference more than 1 will just waste candies. The difference sometimes must be greater than 1, but I'll get to when that happens later.
Now on to finding the kids who should get only one candy. I visualise the ratings as a mountain range (The greater the rating the higher the mountains at that point) and finding the kids who should get one candy as finding valleys (points where both neighbours have a higher rating or the same rating) in the mountain range. The example given would look like (the valleys are indicated by the arrows):
*** *
**** **
****** **
*********
^ ^ ^
For the purpose of this process I assume there are 2 peaks of "infinite" height before the beginning and after the end of this line. (When I say infinite I just mean larger than any possible value in the input so you can just use 10^5+1 for "infinity". In practice, I'd use a value larger than that in case the problem setters have bugged input data.)
You can easily find the valleys using the following code:
ratings = ...
N = ...
valleys = []
def get_rating(i):
if i < 0 or i > N-1:
return INFINITY
return ratings[i]
for i from 0 to N-1:
if get_rating(i) <= get_rating(i-1) and get_rating(i) <= get_rating(i+1):
valleys.append(i)
The array valleys contains the indices of the valleys. We know each kid representing a valley should get one candy. For illustration assume the valley is at index 4. Now we know the kids at index 3 and 5 should get at least 2 candies. If the kid at index 2 has a higher rating than the kid at index 3 that kid should get at least 3 candies. And so on for 2 and down. Similarly for 6 and up.
Note I say "at least", this is because of peaks (kids whose ratings are higher than both of their neighbour's, note unlike valleys I don't include equality in this definition). Peaks can have two minimum constraints and we simply choose the greater of the two.
Now we can find the number of candies each kid should get with the following code:
candies = [0] * N # An array of N 0s
for valley_idx in valleys:
candies[valley_idx] = 1
cur_idx = valley_idx-1
cur_candies = 2
while cur_idx >= 0 and ratings[cur_idx] > ratings[cur_idx+1]:
candies[cur_idx] = max(candies[cur_idx], cur_candies)
cur_idx -= 1
cur_candies += 1
cur_idx = valley_idx+1
cur_candies = 2
while cur_idx < N and ratings[cur_idx] > ratings[cur_idx-1]:
candies[cur_idx] = max(candies[cur_idx], cur_candies)
cur_idx += 1
cur_candies += 1
Then the number of candies the teacher needs to buy is the sum of the values in the candies array.
Doing this the answer turns out to be 18 for our sample input or in the form of a graph:
* * *
** ** **
*********
In the above solution I assumed that adjacent kids with the same rating don't place any restrictions on the amount of candy either should get with relation to the other. If it is instead the case that both kids need to get the same amount of candy we can quite easily alter the algorithm to take this into account.
The basic idea is that we do a sort of run length encoding, because we can notice that whether there are 1 or more kids in a row that have the same rating it doesn't alter the amount of candies their neighbours should get. We need to keep track of the number of kids in a row though since 5 kids in a row getting 5 candies means we have to dole out 25 candies and not just 5. We do this with a multipliers array. Using the following code we find the new ratings array and the multipliers array:
new_ratings = [ratings[0]]
multipliers = [1]
for i from 1 to N-1:
if ratings[i] == new_ratings[len(new_ratings)-1]:
multipliers[len(new_ratings)-1] += 1
else:
new_ratings.append(ratings[i])
multipliers.append(1)
Now we just run the original algorithm on the new_ratings array and get a candies array. Then to get the actual amount of candies we can just run:
answer = 0
for i from 0 to len(new_ratings)-1:
answer += multipliers[i] * candies[i]
Doing this the answer turns out to be 20 for our sample input or in the form of a graph:
*** *
***** **
*********
我使用简单的DP方法来解决这个问题。如果您获得的评分大于前一个评分，则增加 DP 表中的第 i 个值，否则可能有两种情况。一个条件是前一个索引的 DP 值为 1，然后以相反的顺序遍历，直到您获得的值小于其下一个值并不断更新 DP。另一个条件是先前索引的 DP 值大于 1，在这种情况下，DP 中的当前索引被分配为 1。
for(int i=1; i <= n; i++){
scanf("%d", ra+i);
if( ra[i] > ra[i-1] )
dp[i] = dp[i-1] + 1;
else if( dp[i-1] == 1 ){
dp[i] = 1;
for( int j=i-1; j>0; j-- )
if( ra[j] > ra[j+1] )
dp[j] = max ( dp[j+1] + 1, dp[j] );
else
break;
}
else
dp[i] = 1;
}
long long sum = 0;
for(int i = 1;i <= n; i++)sum+= dp[i];
printf("%lld\n",sum);
实际上这个问题可以通过在数组上传递两次来解决。解决方案将是 O(N) 时间。我通过使用 geeksforgeeks Trapping Rain Water ( http://www.geeksforgeeks.org/trapping-rain-water/ ) 问题解决了这个问题。同样的原则也适用于这个问题。
首先，我们有两个规则。- 每个学生至少得到 1 颗糖果。- 每个比他/她的邻居（下一个或上一个学生）评分更高的学生都会比他们至少多得到一个糖果。
正如我所说，我们需要两个通过数组。第一个是从左到右；- 首先我们会给第一个糖果分配一个糖果。- 然后通过检查当前学生是否有更大的评分来循环数组，然后给他一个比前一个学生多一个，否则给他 1 个糖果。
第二遍将是从右到左。- 这次我们首先将一颗糖果分配给最后一颗。- 然后从右到左循环数组并在第一个循环中执行类似的操作。
在这两个循环之后，我们将通过获取数组的最大值来循环左右，并将这个值添加到糖果总数中。
测试用例 ：
输入：{ 1, 2, 2 }
输出：{ 1, 2, 1 } => 4
输入：{ 9, 2, 3, 4, 4, 4, 2, 1, 3, 4 }
输出：{ 2, 1, 2, 3, 1, 3, 2, 1, 2, 3 } => 20
您可以在下面找到针对此问题的 Java 解决方案。
public int calculate(int[] arr) {
int m = arr.length;
int[] left = new int[m];
int[] right = new int[m];
int candies = 0;
left[0] = 1;
for (int i = 1; i < m; i++)
left[i] = arr[i] > arr[i - 1] ? left[i - 1] + 1 : 1;
right[m - 1] = 1;
for (int i = m - 2; i >= 0; i--)
right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 1;
for (int i = 0; i < m; i++)
candies += Math.max(left[i], right[i]);
return candies;
}
假设我们有
1, 5, 2, 10, 10 3, 8, 9 , 1 , 1, 2 作为 11 名 S1 至 S11 学生的评分
假设我们在 y 轴上绘制评分与学生的图表，然后
局部最小值总是会得到一颗糖果，因此学生 S1、S3、S6、S9 和 S10 将是局部最小值并且会得到一颗糖果。我们可以通过说存在一个与我们所说的不同的最小解决方案（So）来争论，然后我们可以创建另一个解决方案（So1），其中所有学生都得到相同的糖果，而偏离的局部最小值得到一个糖果，那么 So1 将是最小值，因此不存在局部最小值获得大于 1 的糖果的最小解。
一旦你得到了局部最小值，你就可以横向左右最小值来计算其他学生的糖果。
对于局部最大值，其相邻节点 +1 的值将更大。工作代码如下，时间复杂度为 O(n)，空间复杂度为 O(n)
public static int candy(ArrayList<Integer> a) {
int size = a.size();
int[] cand = new int[size];
// give all children candies equal to 1
// local minimas will get 1
for(int i = 0; i < size; i++)
{
cand[i] = 1;
}
// increase count on the right of local minimas
for(int i = 1; i < size; i++)
{
if(a.get(i) > a.get(i-1))
{
cand[i] = cand[i-1]+1;
}
}
// increase count on the left of local minimas
// local maximas should be max of left and right
for(int i = size-2; i >= 0; i--)
{
if(a.get(i) > a.get(i+1))
{
cand[i] = Math.max(cand[i], cand[i+1]+1);
}
}
// get the sum
int count = 0;
for(int i = 0; i < size; i++)
{
count = count + cand[i];
}
return count;
}
您可以在 HackerEarth Problem 使用测试用例进行测试：https ://www.hackerrank.com/challenges/candies
Leetcode：https ://leetcode.com/problems/candy/
你可以找到更详细的解释为什么这有效@http ://stackandqueue.com/ ?p=108
一个非常简单的实现
空间复杂度：O(n) 时间复杂度：O(n)
步骤1：开始从左到右遍历数组，并将值1分配给dp数组中的每个索引。
第2步：开始从左到右遍历数组，如果这个人得分更多，那么坐在他左边的那个人的dp就是dp[i-1]+1；
第 3 步：开始从右到左遍历数组，如果这个人得分更多，那么坐在他右边的那个人的 dp 将是 max(dp[i],dp[i+1]+1);
第 4 步：添加 dp 数组中的所有值。
#include<bits/stdc++.h>
using namespace std;
long int arr[100005];
long int dp[100005];
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%ld",&arr[i]);
long int ans=0;
dp[0]=1;
for(i=1;i<n;i++)
{
if(arr[i]>arr[i-1])
dp[i]=dp[i-1]+1;
else
dp[i]=1;
}
for(i=n-2;i>=0;i--)
{
if(arr[i]>arr[i+1])
dp[i]=max(dp[i],dp[i+1]+1);
}
for(i=0;i<n;i++)
{
ans=ans+dp[i];
}
cout<<ans<<endl;
return 0;
}
也许是最简单的解决方案：
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int children;
int sum=0;
cin >> children;
int ratings[children];
int candies[children];
//give all children 1 candy to start
for(int i=0;i<children;++i)
{
cin >> ratings[i];
candies[i] = 1;
}
//if the current child has a better rating than the child
//before him he is entitled to +1 greater candy than that child
for(int i=1;i<children;++i)
{
if(ratings[i] > ratings[i-1])
candies[i] = candies[i-1]+1;
}
// work backwards to break any discrepancies ex.
// rating[5,4,3] -> candies[1,1,1] -> candies [1,1,1] -> candies [3,2,1]
// starting ratings give everyone 1 first loop second loop
for(int i=children-1;i>=0;--i)
{
if(ratings[i] > ratings[i+1])
{
candies[i] = max(candies[i],candies[i+1]+1);
}
}
for(int i=0;i<children;++i)
{
sum+=candies[i];
}
cout << sum;
return 0;
}
我使用两个队列来存储未分配索引的递增和递减序列，并枚举相邻评分的所有可能情况，并在评分达到高原或底部时分配糖果（即当当前评分为局部最小值或与以前相同时）。
这是我的解决方案：
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <deque>
void assigncandies(std::deque<int>& incr, std::deque<int>& decr, unsigned int& total) {
int incrlen = incr.size();
int decrlen = decr.size();
if (incrlen >= decrlen) {
int num=incrlen;
int last = incr.back();
while(!incr.empty()) {
int idx = incr.back();
total += num;
incr.pop_back();
num --;
}
if (!decr.empty()) {
if (last == decr.front()) decr.pop_front();
num=1;
while(!decr.empty()) {
int idx = decr.back();
//candies[idx]=num;
total += num;
decr.pop_back();
num ++;
}
}
} else {
int num=decrlen;
int last = decr.front();
while (!decr.empty()) {
int idx = decr.front();
//candies[idx]=num;
total += num;
decr.pop_front();
num --;
}
if (!incr.empty()) {
if (last == incr.back()) incr.pop_back();
num=1;
while(!incr.empty()) {
int idx = incr.front();
//candies[idx]=num;
total += num;
incr.pop_front();
num ++;
}
}
}
}
int main () {
int N;
unsigned int total=0;
int PrevR, CurR, NextR;
std::cin >> N;
std::deque<int> incr;
std::deque<int> decr;
for (int i = 0; i<N;i++) {
if (i==0) {
std::cin>>CurR;
std::cin >> NextR;
} else if (i != N-1) std::cin >> NextR;
if (i==0) {
if (CurR>NextR) decr.push_back(0);
else if (CurR<NextR) incr.push_back(0);
else total=1;
} else if (i==N-1) {
if (PrevR<CurR) {
incr.push_back(i);
}
if (PrevR>CurR) {
decr.push_back(i);
}
if (PrevR==CurR) {
total += 1;
}
assigncandies(incr,decr,total);
} else {
if (PrevR == CurR && CurR == NextR) {
assigncandies(incr,decr,total);
total += 1;
}
if (PrevR == CurR && CurR < NextR) {
assigncandies(incr,decr,total);
incr.push_back(i);
}
if (PrevR == CurR && CurR > NextR) {
assigncandies(incr,decr,total);
decr.push_back(i);
}
if (PrevR < CurR) {
incr.push_back(i);
if (CurR > NextR) decr.push_back(i);
}
if (PrevR > CurR && CurR >= NextR) {
decr.push_back(i);
}
if (PrevR > CurR && CurR < NextR) {
decr.push_back(i);
assigncandies(incr,decr,total);
total -= 1;
incr.push_back(i);
}
}
PrevR = CurR;
CurR = NextR;
}
std::cout<<total<<std::endl;
return 0;
}
它通过了测试用例并且 3/10 用例正确，但其余部分我遇到了分段错误。
我想知道是否有人可以指出我的代码有什么问题。
非常感谢！
我觉得这可能是可能的解决方案之一......
def candy(N,r):
H=[0]*N
R=r
cur_can=1
cand=[0]*N
cand[0]=1
#print R#,'\n',cand
for i in range(0,N):
if i!=0:
#print R[i],' ',R[i-1]
if R[i]>R[i-1]:
cand[i]=cand[i-1]+1
else:
cand[i]=1
## print R[i],i
sum=0
## print i
print cand
for j in range(0,N):
sum+=cand[j]
return sum
r=[1,2,2,4,1,2,4]
N=len(r)
print candy(N,r)
在 th 代码中用作样本的值的输出给出了 12 作为答案，这对我来说似乎是正确的......你怎么看？
我不认为这是一个非常困难的问题。如果你仔细想想，你会得到你自己的答案。
#include <iostream>
#include <queue>
using namespace std;
#define CALC(n) (n)+(n)*((n)-1)/2
struct PAIR {
int n;int up;//up=0,1,2; 0是升，1是平，2是降
public:
PAIR(int _n,int _u){
n=_n;up=_u;
}
};
int N;
queue<PAIR> q;
int calc(int up,int p){
if(up==1)
return p;
else {
return p+p*(p-1)/2;
}
}
int getType(int lc,int c){
int up=-1;
if(c>lc)
up=0;
else if(c==lc)
up=1;
else
up=2;
return up;
}
int main(int argc, const char * argv[])
{
scanf("%d",&N);
int lastChild,child,n=2;
long long result=0;
scanf("%d%d",&lastChild,&child);N-=2;
int up=getType(lastChild, child);
lastChild=child;
while (N--) {
scanf("%d",&child);
int tu=getType(lastChild, child);
if(tu==up)
n++;
else {
q.push(PAIR(n,up));
n=2;
up=tu;
}
lastChild=child;
}
q.push(PAIR(n,up));
q.push(PAIR(1,1));
/*其实主要就是看转折点是属于上一段还是当前段。
如果是正V的话，转折点属于后一段。前一段的和-1.
如果是倒V的话，转折点属于长的一段。
然后是平的和别的有搭配的话，转折点属于别的
*/
PAIR lastp=q.front();q.pop();
while(q.size()){
PAIR pir=q.front();q.pop();
if(pir.up==1){
result+=calc(lastp.up,lastp.n);//如果下一段是平的，就把转折点分到上一段
pir.n-=1;
}
else if(lastp.up==1){
result+=calc(lastp.up,lastp.n-1);//如果上一段是平的，就把转折点分到下一段
} else if((lastp.up==0)&&(pir.up==2)){//如果是倒V型的，转折点属于长的
if(lastp.n>pir.n){
result+=calc(lastp.up,lastp.n);
pir.n-=1;
} else {
result+=calc(lastp.up,lastp.n-1);
}
} else if((lastp.up==2)&&(pir.up==0)){//如果是正V型的，转折点属于后一个
result+=calc(lastp.up,lastp.n)-1;
} else {
printf("WRONG!");
}
lastp=pir;
}
printf("%lld\n",result);
return 0;
}
总结一下：
#include <vector>
#include <iostream>
using namespace std;
int main() {
int N;
cin>>N;
vector<int> A(N,0),B(N,1);
for(int i=0;i<N;++i) cin>>A[i];
for(int i=0;i<N;++i) if(A[i]>A[i-1]) B[i]=B[i-1]+1;
for(int j=N-2;j>=0;--j) if (A[j]>A[j+1]) B[j] = max(B[j], B[j+1]+1);
int sum=0;
for(int i=0;i<N;++i) sum+=B[i];
cout<<sum<<endl;
return 0;
}
1.Ratings[]使用给定的评级初始化。
2.我们先给Candy每个孩子1个。所以用 1 初始化所有成员Val[]。
3.现在遍历并检查两个相邻的孩子（i + 1和i - 1）是否满足条件。
4.继续这样做，直到我们得到一个条件永远不会被破坏的完整遍历。那我们就完成了！
bool done = false;
while (!done)
{
done = true;
for (int i = 0 to i = Ratings.size() - 1)
{
for (int k = 1 and k = -1)
{
int adjacent = i + k;
if (adjacent >= 0 && adjacent < N)
{
if (Ratings[adjacent] > Ratings[i] && Val[adjacent] <= Val[i])
{
Val[adjacent] = Val[i] + 1;
done = false;
}
}
}
}
}
# this python code solves the problem for all test cases on interviewstreet
#!/usr/bin/python
if __name__ == "__main__":
N = int(raw_input().strip())
scores = []
for i in range(N):
scores.append(int(raw_input().strip()))
nc = []
if(scores[0]>scores[1]):
nc.append(-1)
else:
nc.append(0)
for i in range(1,N-1):
if (scores[i] > scores[i-1]) and (scores[i]>scores[i+1]):
nc.append(2)
elif (scores[i] > scores[i-1]):
nc.append(1)
elif (scores[i]>scores[i+1]):
nc.append(-1)
else:
nc.append(0)
if(scores[N-1]> scores[N-2]):
nc.append(1)
else:
nc.append(0)
noc = []
for i in range(N):
noc.append(0)
for i in range(N):
if(nc[i]==0):
noc[i] = 1
for i in range(N):
if(nc[i]==1) and (noc[i-1]!=0):
noc[i] = noc[i-1]+1
for i in range(N-1,-1,-1):
if(nc[i]==-1) and (noc[i+1]!=0):
noc[i] = noc[i+1]+1
for i in range(N):
if(nc[i]==2) and (noc[i-1]!=0) and (noc[i+1]!=0):
noc[i] = max((noc[i-1],noc[i+1]))+1
nt = sum(noc)
print nt
想想这些可能的评级配置：1 2 3 4 5 或任何递增序列和 5 4 3 2 1 或任何递减序列
在第一种情况下可以做什么？1 2 3 4 5 是在第二种情况下分配的糖果 5 4 3 2 1
可以通过从左到右扫描阵列并识别增加的间隔并从右到左扫描并再次识别增加的间隔并在此过程中分配最少数量的糖果来获得解决方案。具体细节请看代码：
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 100000
int c[N];
int val[N];
int solve(int n)
{
int res=n;
int i=0,value=0;
while(i<n)
{
value=0;
i+=1;
while(i<n && c[i]>c[i-1])
{
value+=1;
val[i]=value;
i+=1;
}
}
i=n-1;
while(i>=0)
{
value=0;
i-=1;
while(i>=0 && c[i]>c[i+1])
{
value+=1;
val[i]=max(val[i],value);
i-=1;
}
}
for(i=0;i<n;++i) res+=val[i];
return res;
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;++i) scanf("%d",&c[i]);
printf("%d\n",solve(n));
return 0;
}
AS mentioned by others,scanning left to right and then right to left,and getting max candies used at certain postion is working.
Before this, i used other way,which seemed to be working and i checked it with many different inputs,although i couldnt clearly write it in code,Here is the Algo:
Algorithm:
1.Use an int[]index array and store all the indexes in the sorted value of thie ranks.
so here
int values[]=9 2 3 6 5 4 3 2 2 2
so index sorted array would be
int index[]= 1 7 8 9 2 6 5 4 3 0
now int[] result=new result[10];
and initialize it with -1.
sending each value from index[]in the order and make sure that each one is satifying the given condtions.
that
i=index;
while(i>=0)
{
if(i-1>=0 && arr[i]>arr[i-1])
break;
if(i-1>=0 && arr[i]<arr[i-1])
result[i-1]=result[i]+1;
else
if(i-1>=0 && arr[i]==arr[i-1])
result[i-1]=1
i--;
}
//similary towards the right
i=index;
while(i<arr.length)
{
if(i+1<arr.length && arr[i]>arr[i+1])
break;
if(i+1<arr.length && arr[i]<arr[i+1])
result[i+1]=1+result[i];
else
if(i+1<arr.length && arr[i]==arr[i+1])
result[i+1]=1
i++;
}
so result array will be like this for index 1
2 1 2 3 - - - - - -
then for index 7
2 1 2 5(its modifed from 3) 4 3 2 1 1
followe by indeices :8 9 2 6 5 4 3 0
which all satifies the condtion and more modification occurs in this case..so total number of candies =22
以数组作为输入的简单工作代码，采用 Java 语言。时间复杂度：O(n)。
import java.util.Arrays;
public class MyClass {
public static void main(String[] args) {
int []childrenRating = {9, 8, 7, 10, 11, 12, 14, 1, 5};
int []expectedDistribution = {3, 2, 1, 2, 3, 4, 5, 1, 2};
int []resultingDistribution = new int[childrenRating.length];
int v = 1;
int k, j = 0;
while(j < childrenRating.length){
k = j;
if(k >0 && childrenRating[k] == childrenRating[k-1]) { v=1; }
resultingDistribution[k] = v;
while(j+1 < childrenRating.length && childrenRating[j+1] < childrenRating[j]){
j++;
}
v = 1;
for(int i = j; i > k; i--){
resultingDistribution[i] = v++;
}
resultingDistribution[k] = Math.max(resultingDistribution[k], v);
j++;
v = resultingDistribution[j-1]+1;
}
if(Arrays.equals(expectedDistribution, resultingDistribution)) {
System.out.println("Correct Distribution");
}
else {
System.out.println("Wrong Distribution!");
}
}
}