leetcode135.分发糖果(相邻的孩子中，评分高的必须糖果更多)思维

class Solution {
public:int candy(vector<int>& a) {int n&＃61;a.size(),sum&＃61;0;if(n<&＃61;1) return n;sum&＃61;1;//pre的用处就是假如[3,7]是下坡 pre的值就是之前3分配的高度,然后[4,7]小朋友分别对应0,-1,-2,-3 这些小朋友都要增加4个糖果, //然后假如pre不大于等于5(第四个小朋友分配了0&＃43;4&＃61;4 所以第三个要>&＃61;5)的话,也要多给第3个小朋友分配糖果for(int i&＃61;0,pre&＃61;1;i<n-1;){if(a[i&＃43;1]>a[i]){int cnt&＃61;1;//第i个小朋友的糖果已经在之前的下坡或者等坡分配好了.while(i<n-1&&a[i&＃43;1]>a[i]) &＃43;&＃43;cnt,sum&＃43;&＃61;cnt,&＃43;&＃43;i;//i&＃43;1(i还没&＃43;&＃43;之前的i&＃43;1)需要分配的糖果是cntpre&＃61;cnt;//更新precontinue;}if(a[i&＃43;1]<a[i]){//i->i&＃43;1 就是下坡了,i现在分配的糖果是pre个int di&＃61;i,cnt&＃61;1;while(i<n-1&&a[i&＃43;1]<a[i]) --cnt,sum&＃43;&＃61;cnt,&＃43;&＃43;i;//i&＃43;1(i还没&＃43;&＃43;之前的i&＃43;1)需要分配的糖果是cntif(cnt<&＃61;0){sum&＃43;&＃61;(i-di)*(1-cnt);//第[di&＃43;1,i]个每个人需要增加(1-cnt)个糖果if(pre<1&＃43;1-cnt) sum&＃43;&＃61;1&＃43;1-cnt-pre;//多给第di个小朋友分配}//下坡之后不会是下坡(否则while不会跳出来),所以不需要更新precontinue;}if(a[i&＃43;1]&＃61;&＃61;a[i]){//比如[1,5]等坡 那么1是取原来的值,[2,5]都取1 然后5或许会被下坡更新(假如5紧跟一个下坡且1满足不了)while(i<n-1&&a[i&＃43;1]&＃61;&＃61;a[i]) sum&＃43;&＃61;1,&＃43;&＃43;i;pre&＃61;1;//更新precontinue;}}return sum;}
};

class Solution {
public:int candy(vector<int>& a) {int n&＃61;a.size(),sum&＃61;0;if(n<&＃61;1) return n;sum&＃61;1;cout<<"第0个小朋友有1个糖果"<<endl;for(int i&＃61;0,pre&＃61;1;i<n-1;){if(a[i&＃43;1]>a[i]){cout<<i<<" --> "<<i&＃43;1<<"开始上坡了"<<endl;int cnt&＃61;1;//第i个小朋友的糖果已经在之前的下坡分配好了.while(i<n-1&&a[i&＃43;1]>a[i]){&＃43;&＃43;cnt,sum&＃43;&＃61;cnt;//i&＃43;1需要分配的糖果是cntcout<<"第"<<i&＃43;1<<"个小朋友有"<<cnt<<"个糖果"<<endl;&＃43;&＃43;i;}pre&＃61;cnt;continue;}if(a[i&＃43;1]<a[i]){//i->i&＃43;1 就是下坡了,i现在分配的糖果是pre个cout<<i<<" --> "<<i&＃43;1<<"开始下坡了"<<endl;int di&＃61;i,cnt&＃61;1;while(i<n-1&&a[i&＃43;1]<a[i]){--cnt,sum&＃43;&＃61;cnt;//第i&＃43;1个小朋友分配cnt个cout<<"第"<<i&＃43;1<<"个小朋友有"<<cnt<<"个糖果"<<endl;//可见第di&＃43;1以及往后分配是从0开始减的&＃43;&＃43;i;}if(cnt<&＃61;0){sum&＃43;&＃61;(i-di)*(1-cnt);//第[di&＃43;1,i]个每个人需要增加(1-cnt)个糖果cout<<"第["<<di&＃43;1<<","<<i<<"]个小朋友每个人需要增加"<<1-cnt<<"个糖果"<<endl;if(pre<1&＃43;1-cnt) {//上面di&＃43;1及以后从0开始减 这里的di取得就是1 本来应该是(1&＃43;1-cnt)的结果前面取了pre个 所以要增加sum&＃43;&＃61;1&＃43;1-cnt-pre;cout<<"第"<<di<<"个小朋友需要增加"<<1&＃43;1-cnt-pre<<"个糖果"<<endl;}}continue;}if(a[i&＃43;1]&＃61;&＃61;a[i]){cout<<i<<" --> "<<i&＃43;1<<"开始等坡了"<<endl;while(i<n-1&&a[i&＃43;1]&＃61;&＃61;a[i]){sum&＃43;&＃61;1;cout<<"第"<<i&＃43;1<<"个小朋友有"<<1<<"个糖果"<<endl;&＃43;&＃43;i;}pre&＃61;1;continue;}}return sum;}
};