【BZOJ】【3850】ZCC Loves Codefires

时间:2022-04-21 09:29:29

贪心


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

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

 /**************************************************************
Problem: 3850
User: ProgrammingApe
Language: C++
Result: Accepted
Time:64 ms
Memory:2052 kb
****************************************************************/ //BZOJ 3850
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=;
typedef long long LL;
struct node{
int t,k;
bool operator < (const node& b) const {
return t*k+(t+b.t)*b.k < b.t*b.k+(t+b.t)*k;
}
}a[N]; int main(){
// freopen("input.txt","r",stdin);
int n;
scanf("%d",&n);
F(i,,n) scanf("%d",&a[i].t);
F(i,,n) scanf("%d",&a[i].k);
sort(a+,a+n+);
LL time=;
LL ans=;
F(i,,n){
time+=a[i].t;
ans+=(LL)a[i].k*time;
}
printf("%lld\n",ans);
return ;
}