首页 > 代码库 > 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