# 一起刷leetcode(135):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?

/*
*Author:qingyuanxings
*Date:2015-03-03
*Title:135.Candy
*Quick sort+Greedy algorithm
*/
include <unordered_map>include <vector>include <iostream>include <algorithm>include <numeric>include <time.h>using namespace std;

class Solution {
public:
int random(int start,int end)
{
srand(time(NULL));
return start+rand()%(end-start+1);
}

void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}

int rand_partition(vector<int> &ratings,vector<int> &positions,int p, int q){
int t=random(p,q);
swap(ratings[t],ratings[p]);
swap(positions[t],positions[p]);
int base=ratings[p];
int i=p;
for(int j=p+1;j<=q;j++)
{
if(ratings[j]<base)
{
i++;
swap(ratings[i],ratings[j]);
swap(positions[i],positions[j]);
}
}
swap(ratings[i],ratings[p]);
swap(positions[i],positions[p]);

return i;
}

//quick sort and record its relative position
void quicksort(vector<int> &ratings,vector<int> &positions,int left,int right){
if(left<right){
int r = rand_partition(ratings,positions,left,right);
quicksort(ratings,positions,left,r-1);
quicksort(ratings,positions,r+1,right);
}
}

int candy(vector<int> &ratings) {
//Position and rating
unordered_map<int,int> pos_map;
int c_size = ratings.size();
//Give one candy to each kid
vector<int> candies(c_size,1);
vector<int> positions(c_size);
for(int i=0;i!=c_size;i++){
positions[i] = i;
pos_map[i] = ratings[i];
}
quicksort(ratings,positions,0,c_size-1);
for(int i=0;i<c_size;i++){
int pos = positions[i];
int temp = pos_map[pos];
if(pos>0){
if(pos_map[pos-1]>temp && candies[pos-1]<=candies[pos]){
candies[pos-1] = candies[pos]+1;
}
}
if(pos<c_size-1){
if(pos_map[pos+1]>temp && candies[pos+1]<=candies[pos]){
candies[pos+1] = candies[pos]+1;
}
}
}
return accumulate(candies.begin(),candies.end(),0);
}
};


## 收藏七月在线，一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~

• APP下载 七月在线APP
• 微信公众号 扫码免费领课
• 返回顶部