首页 > 代码库 > 【BZOJ】【3850】ZCC Loves Codefires

【BZOJ】【3850】ZCC Loves Codefires

2024-10-26 17:34:02   210人阅读

贪心，就跟NOIP2012国王游戏差不多，考虑交换相邻两题的位置，对其他题是毫无影响的，然后看两题顺序先后哪个更优。sort即可。

WA了一次的原因：虽然ans开的是long long，但是在这一句:ans+=time*a[i].k;时，还是需要在time（int类型）前面加上(LL)进行类型强制转换。

技术分享
 1 /************************************************************** 2     Problem: 3850 3     User: ProgrammingApe 4     Language: C++ 5     Result: Accepted 6     Time:64 ms 7     Memory:2052 kb 8 ****************************************************************/ 9  10 //BZOJ 385011 #include<cstdio>12 #include<cstring>13 #include<cstdlib>14 #include<iostream>15 #include<algorithm>16 #define rep(i,n) for(int i=0;i<n;++i)17 #define F(i,j,n) for(int i=j;i<=n;++i)18 #define D(i,j,n) for(int i=j;i>=n;--i)19 using namespace std;20 const int N=100086;21 typedef long long LL;22 struct node{23     int t,k;24     bool operator < (const node& b) const {25         return t*k+(t+b.t)*b.k < b.t*b.k+(t+b.t)*k;26     }27 }a[N];28  29 int main(){30 //  freopen("input.txt","r",stdin);31     int n;32     scanf("%d",&n);33     F(i,1,n) scanf("%d",&a[i].t);34     F(i,1,n) scanf("%d",&a[i].k);35     sort(a+1,a+n+1);36     LL time=0;37     LL ans=0;38     F(i,1,n){39         time+=a[i].t;40         ans+=(LL)a[i].k*time;41     }42     printf("%lld\n",ans);43     return 0;44 }
View Code

 

【BZOJ】【3850】ZCC Loves Codefires


联系
我们