Codeforces Round #540 (Div. 3) D1. Coffee and Coursework (Easy version) 【贪心】
任意门：http://codeforces.com/contest/1118/problem/D1
The only difference between easy and hard versions is the constraints.
Polycarp has to write a coursework. The coursework consists of m pages.
Polycarp also has completely (i.e. he cannot split any cup into several days).
Surely, courseworks are not usually being written in a single day (in a perfect world of Berland, at least). Some of them require multiple days of hard work.
Let's consider some day of Polycarp's work. Consider Polycarp drinks max(0,aik−k+1) pages.
If Polycarp doesn't drink coffee during some day, he cannot write coursework at all that day.
Polycarp has to finish his coursework as soon as possible (spend the minimum number of days to do it). Your task is to find out this number of days or say that it is impossible.
The first line of the input contains two integers 1≤m≤104) — the number of cups of coffee and the number of pages in the coursework.
The second line of the input contains i-th cup.
If it is impossible to write the coursework, print -1. Otherwise print the minimum number of days Polycarp needs to do it.
5 8 2 3 1 1 2
4
7 10 1 3 4 2 1 4 2
2
5 15 5 5 5 5 5
1
5 16 5 5 5 5 5
2
5 26 5 5 5 5 5
-1
In the first example Polycarp can drink fourth cup during first day (and write 4. It is obvious that there is no way to write the coursework in three or less days in this test.
In the second example Polycarp can drink third, fourth and second cups during first day (and write 2. It is obvious that Polycarp cannot write the whole coursework in one day in this test.
In the third example Polycarp can drink all cups of coffee during first day and write 5+(5−1)+(5−2)+(5−3)+(5−4)=15pages of coursework.
In the fourth example Polycarp cannot drink all cups during first day and should drink one of them during the second day. So during first day he will write 5 pages of coursework. This is enough to complete it.
In the fifth example Polycarp cannot write the whole coursework at all, even if he will drink one cup of coffee during each day, so the answer is -1.
题意概括：
给出 N 杯咖啡所具有的能量值，和需要看完的书。
喝一杯咖啡可以获得一定的能量值，看一页书消耗一个能量值，在一天内喝多次咖啡效果会递减，求最少多少天可以看完所有的书
解题思路:
一开始看错题目。。。以为是要喝完全部的咖啡并且刚好凑足所需的能量值。。。。
其实就是一道贪心水题，因为没有规定要喝完，而且只要能量值大于等于所需能量值即可。
枚举所需的最小天数，第 K 大的数在第 K 天用这样达到的结果肯定是最优的。
如果全部能量值加起来都不够说明无解。
AC code：
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define LL long long 4 using namespace std; 5 const int MAXN = 101; 6 const int MAXM = 1e4+10; 7 int num[MAXM]; 8 int N, M; 9 bool cmp(int a, int b){return a > b;} 10 11 int main() 12 { 13 int ans = 0; 14 bool flag = false; 15 int tot = 0, cnt = 0; 16 scanf("%d %d", &N, &M); 17 for(int i = 1; i <= N; i++){ 18 scanf("%d", &num[i]); 19 tot+=num[i]; 20 } 21 if(tot < M) puts("-1"); 22 else{ 23 tot = 0; 24 cnt = 0; 25 sort(num+1, num+1+N, cmp); 26 for(int ans = 1; ans <= N; ans++){ 27 tot = 0;cnt = 0;flag = false; 28 for(int i = 1; i <= N; i++){ 29 tot+=max(0, num[i]-cnt); 30 if(i%ans == 0) cnt++; 31 if(tot >= M){ 32 flag = true; 33 break; 34 } 35 } 36 if(flag){ 37 printf("%d ", ans); 38 break; 39 } 40 } 41 } 42 return 0; 43 }