首页 > 代码库 > Candy
Candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
class Solution { public: int candy(vector<int> &ratings) { int n=ratings.size(); if(n<2) return n; int candys[n]; for(int i=0;i<n;i++) candys[i]=0; int cnt=0; while(cnt<n) { for(int i=0;i<n;i++) if(candys[i]==0) { if((i==0 && (ratings[i+1]>=ratings[i]||candys[i+1]>0)) || (i==n-1 && (ratings[i-1]>=ratings[i] || candys[i-1]>0))) { if(i==0) { if(ratings[1]==ratings[0]) candys[0]=1; else candys[0]=candys[1]+1; } else { if(ratings[n-1]==ratings[n-2]) candys[n-1]=1; else candys[n-1]=candys[n-2]+1; } cnt++; if(i>0 && candys[i-1]==0) i=i-2; continue; } if(i>0 && i<n-1 && (candys[i-1]>0 || ratings[i-1]>=ratings[i]) && (candys[i+1]>0 || ratings[i+1]>=ratings[i])) { candys[i]=1; if(ratings[i-1]<ratings[i]) candys[i]=candys[i-1]+1; if(candys[i]<=candys[i+1] && ratings[i+1]<ratings[i]) candys[i]=candys[i+1]+1; cnt++; if(i>0 && candys[i-1]==0) i=i-2; continue; } } } int sum=0; for(int i=0;i<n;i++) sum=sum+candys[i]; return sum; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。