首页 > 代码库 > 【贪心】bzoj3850 ZCC Loves Codefires
【贪心】bzoj3850 ZCC Loves Codefires
类似某noip国王游戏。
考虑交换两个题目的顺序，仅会对这两个题目的贡献造成影响。
于是sort，比较时计算两个题目对答案的贡献，较小的放在前面。
#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;struct Point{ll T,K;}a[100001];bool operator < (const Point &a,const Point &b){return a.T*a.K+(a.T+b.T)*b.K<b.T*b.K+(a.T+b.T)*a.K;}int n;ll ans,sum;int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%lld",&a[i].T); for(int i=1;i<=n;++i) scanf("%lld",&a[i].K); sort(a+1,a+n+1); for(int i=1;i<=n;++i) { sum+=a[i].T; ans+=sum*a[i].K; } printf("%lld\n",ans); return 0;}【贪心】bzoj3850 ZCC Loves Codefires
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。