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?
先对ratings进行排序，从小到大发糖果。
发糖果时判断：左右两边的人是否分数比自己小，若是，则糖果数比他们大即可。
细节：两个人分数一样时糖果数不一定一样。
class Solution { public: int n; int * c; vector<pair<int,int>> a; int candy( vector< int >& ratings) { n = ratings.size(); c = (int*)calloc(n + 10, sizeof(int)); for(int i = 0 ; i < n ; i++) a.push_back( make_pair( ratings[ i ] , i ) ); sort( a.begin() , a.end() ); int ans = 0 ; for(int i = 0; i < n; ++ i) { int x = a[i].second; c[x] = 1; if (x > 0 && c[x - 1] && ratings[x] > ratings[x - 1]) c[x] = c[x - 1] + 1; if (x < n - 1 && c[x + 1] && ratings[x] > ratings[x + 1]) c[x] = max(c[x], c[x + 1] + 1); ans += c[x]; } return ans; } };
