首页 > 代码库 > Uva1149
Uva1149
每个bin最多只能放两个,所以最佳的贪心策略是从大的开始放,如果有空间放第二个,尽量放最大的。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 100000 + 10; 6 7 int t; 8 9 int n,l;10 11 int a[maxn];12 13 int b[maxn];14 15 int flag[maxn];16 17 void solve(){18 int cnt = 0;19 memset(flag, 0, sizeof(flag));20 for(int i = 1; i <= n; ++i){21 if(flag[i]){22 continue;23 } else {24 ++cnt;25 flag[i] = 1;26 int temp = l - a[i];27 int loc = upper_bound(b+1, b+1+n, temp) - b;28 if(loc == 1+n) loc = n;29 for(int j = loc; j >= 1; --j){30 if(!flag[n-j+1] && b[j] <= temp){31 flag[n-j+1] = 1;32 break;33 }34 }35 }36 }37 printf("%d\n",cnt);38 if(t) printf("\n");39 }40 41 bool cmp(int a, int b){42 return a > b;43 }44 45 int main(){46 scanf("%d",&t);47 while(t--){48 scanf("%d%d",&n,&l);49 for(int i = 1; i <= n; ++i){50 scanf("%d",&a[i]);51 b[i] = a[i];52 }53 if(l == 0){54 printf("0\n");55 continue;56 }57 sort(a+1, a+1+n, cmp);58 sort(b+1, b+1+n);59 solve();60 }61 }
Uva1149
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。