題目鏈接

貪心求解，a.atk/a.time值較大的排在前邊。但是這樣使用除法會導致精度損失，compare函數中的比較規則變為a.atk*b.time>b.atk*a.time就行了。當相等的時候按照atk的大小進行排序就行。
(原先的時候想按照a.atk/a.hp值較大的排在前邊，想了一下是不行的。因為hp不同的怪獸攻擊的次數可能是一樣的。)

代碼：

#include <iostream> #include <algorithm> using namespace std; const int inf=1e5+7; int cnt[2*inf]; struct node {int hp;int atk; int time; }arr[inf]; bool compare(node a,node b) { if( a.atk*b.time ==b.atk *a.time )return a.atk >b.atk ; else return a.atk*b.time > b.atk*a.time; }int main( ) {int T,n;int kk=1,k=0;for(int i=1;i<=2*inf;i=i+(++kk)){while(++k<=i) // 7,8,9,10是四。 {cnt[k]=kk; //其中的k應該是生命值。 }k--;} /*for(int i=0;i<=100;i++)cout<<i<<" "<<cnt[i]<<endl;*/int kkk=0;scanf("%d",&T);while(T--){scanf("%d",&n);int abc;for(int i=0;i<n;i++){scanf("%d %d",&arr[i].hp,&arr[i].atk);arr[i].time =cnt[arr[i].hp];} sort(arr,arr+n,compare);long long now=0;for(int i=0;i<n;i++){ now+=arr[i].atk;} long long ans=0;for(int i=0;i<n;i++){ans+=( now * arr[i].time );now-=arr[i].atk;} printf("Case #%d: %lld\n",++kkk,ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的H. Fight Against Monsters的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。