首页 > 代码库 > hdu 6011 Lotus and Characters

hdu 6011 Lotus and Characters

BC的A题 不过被疯狂hack

因为有的人一开始认为只需要计算所有正权值 包括我也是

不过写一下就知道了 就算有负权 仍然可能对ans有贡献

比赛时候的代码可能是改的太匆忙了 到底还是被hack了……

还好B题留到最后了了 要不BC就血崩了……

 

 1 #include<bits/stdc++.h> 2 #define cl(a,b) memset(a,b,sizeof(a)) 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 4 using namespace std; 5 typedef long long ll; 6  7 const int maxn=3e3+10; 8  9 int letter[maxn];10 11 int main()12 {13     int T;14     scanf("%d",&T);15     while(T--)16     {17         cl(letter,0);18         int n,cnt=0;19         scanf("%d",&n);20         for(int i=0;i<n;i++)21         {22             int x,val;23             scanf("%d%d",&x,&val);24             while(val--) letter[cnt++]=x;25         }26         sort(letter,letter+cnt);27         int ans=0,num=cnt;28         while(cnt--)29         {30             int last=ans;31             for(int i=cnt+1;i<num;i++)32                 ans+=letter[i];33             if(ans+letter[cnt]<last)34             { //计算每个权值对ans是否有贡献35                 ans=last;36                 break; //没有贡献的话ans就是上一次的ans37             }     38             else ans+=letter[cnt]; //有贡献继续计算39         }40         if(ans<0) printf("0\n");41         else printf("%d\n",ans);42     }43     return 0;44 }45 /*46 47 248 249 5 150 6 251 352 -5 353 2 154 1 155 56 */

 

hdu 6011 Lotus and Characters