问题描述:
排队抓娃娃,每个人抓到一个娃娃后离开,设每个人抓娃娃所花时间为time,每个人等待的时间为第i~i-1所用时间,第一个人等待的时间为0。如果等待的时间超过抓到娃娃的所用时间,则这个人不开心。
给定一个序列为每个人抓到娃娃的所用时间,求如何排列,使得不开心人数最少。
输入第一行n个人,输入第二行每个人所用时间
input:
4
1 2 3 5
output:
1
参考代码如下:
#include <iostream>#include <algorithm>using namespace std;int NoHappy(int num[], int n){int* cost;int* wait;cost = new int[n];wait = new int[n];int count = 1; //统计最大开心人数 sort(num, num+n);for(int i = 0; i < n; i++){if(i == 0){ cost[i] = num[i];wait[i] = 0; }else{wait[i] = wait[i-1] + cost[i-1];for(int j = i; j < n; j++){if((num[j] - wait[i]) >= 0){cost[i] = num[j];count++;break;}} }} int unhappy = n - count;return unhappy;}int main(){int n, precost;cin >> n;int* cost;cost = new int[n];for(int i = 0; i < n; i++){cin >> cost[i]; }cout << NoHappy(cost,n);}
如果觉得《排队抓娃娃》对你有帮助,请点赞、收藏,并留下你的观点哦!