斓少摘苹果

Time Limit: 3000/3000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status 斓少家的院子里有NN棵苹果树，每到秋天树上就会结出FiFi个苹果。

苹果成熟的时候，斓少就会跑去摘苹果。

斓少摘苹果的方式非常的奇特，每次最多可以选择MM个苹果并摘下来。

但是摘下来的苹果两两一定不是来自同一棵树，问斓少最少摘多少次，才能使得每个苹果都被摘下来呢？

Input 第一行输入一个数NN和MM（1≤M≤N≤1061≤M≤N≤106），代表苹果树的数量，和斓少每次最多摘多少个。

第二行输入NN个数，第ii个数FiFi（0≤Fi≤1060≤Fi≤106）代表这一棵树上一共有多少个苹果

Output 输出一个数字，表示最少选择次数

Sample input and output

5 3 Sample Input Sample Output

3 2 3 2 4 5 Hint 样例可以选 (1,3,5) (2,3,5) (1,4,5) (1,2,5) (3,4) 共5次

要是数据小点估计我都当成模拟来写了，数据很大，模拟铁定不行，找下规律，贪心策略考虑两种情况 1.首先如果n <= m 那肯定就是最多树上的了 2.否则就是总数/m的次数

#include <cstdio> #include <algorithm> using namespace std; #define LL long long LL arr[1000000]; bool cmp(LL x, LL y) { return x > y; } int main() { LL n, m; LL sum = 0; LL ans; scanf("%lld%lld",&n,&m); for(int i = 0;i < n; i++) { scanf("%lld",&arr[i]); sum += arr[i]; } sort(arr,arr+n,cmp); if(sum%m==0) ans = sum/m; else ans = sum/m + 1; if(n <= m) printf("%lld\n",arr[0]); else printf("%lld",ans); return 0; }