首页 > 代码库 > [HDU 5090] Game with Pearls (贪心)
[HDU 5090] Game with Pearls (贪心)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5090
题目大意：给你n个数，问你给若干个数增加c*k(c>=0)能否组成1,2,3,4,5,...,n？
今天下午作比赛的时候，我先用了个dfs，看这个a[i]匹配的是1到n的哪个数。
后来TLE到死。。。
仔细想想，首先，如果这个数是小的数的话，那么它可以匹配很多种，因此如果先将它匹配掉了会浪费，因为它“能力”大。
因此就可以排个序，从大到小进行匹配。
我也不知道怎么用数学语言去证明。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <map> 7 #include <set> 8 #include <queue> 9 #include <string>10 #include <functional>11 using namespace std;12 13 int vis[110];14 int a[110];15 int N,K;16 bool flag;17 18 int main(){19 int M;20 scanf("%d",&M);21 22 while(M--){23 flag = true;24 memset(vis,0,sizeof(vis));25 scanf("%d%d",&N,&K);26 for(int i=0;i<N;i++){27 scanf("%d",&a[i]);28 }29 sort(a,a+N,greater<int>() );30 int i;31 for(i=N;i>=1;i--){32 for(int j=0;j<N;j++){33 if( a[j]<=i&&!vis[j]&&(i-a[j])%K==0 ){34 vis[j]=1;35 break;36 }37 }38 }39 for(int i=0;i<N;i++){40 if( !vis[i] ) {41 flag = 0;42 break;43 }44 }45 if(flag) puts("Jerry");46 else puts("Tom");47 }48 return 0;49 }50 51 /*52 1053 3 154 1 2 355 3 156 0 0 057 3 258 2 2 359 3 260 0 1 361 5 162 1 2 3 4 563 6 264 1 2 3 4 5 565 */
[HDU 5090] Game with Pearls (贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。