2015 Google code jam Qualification Round B 枚举 + 贪心

题意：给你一个无穷长的数列和一些非 0 的值，可以进行两种操作。

1）数列中所有大于1的值都减1

2）从 a[i] 中取出任意的值分给任意人。

问你最少执行多少步能使的数列全为0.

解题思路：枚举最大的a[i]。大于 a[i]的部分都分出去。

解题代码：

 1 // File Name: b.cpp
 2 // Author: darkdream
 3 // Created Time: 2015年04月11日 星期六 23时16分58秒
 4 
 5 #include<vector>
 6 #include<list>
 7 #include<map>
 8 #include<set>
 9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25 
26 using namespace std;
27 int t; 
28 int n; 
29 int a[1005];
30 int main(){
31     freopen("B-large.in","r",stdin);
32     freopen("output","w",stdout);
33     scanf("%d",&t);
34     for(int CA = 1; CA <= t; CA ++)
35     {
36         scanf("%d",&n);
37         int MX = 0 ; 
38         for(int i= 1;i <=n;i ++){
39             scanf("%d",&a[i]);
40             MX = max(MX,a[i]);
41         }
42         int ans = 1e9;
43         
44         for(int i = 1;i <= MX ;i ++){
45             int sum = i ; 
46             for(int j = 1;j <= n;j ++)
47             {
48                 if(a[j] > i)
49                 {
50                   if(a[j] % i == 0 )
51                   {
52                     sum += a[j]/i - 1; 
53                   }else sum += a[j]/i ; 
54                 }
55             }
56             ans = min(sum,ans);
57         }
58         printf("Case #%d: %d
",CA,ans);
59     }
60 return 0;
61 }

View Code