c/c++语言开发共享Protecting the Flowers

Protecting the Flowers简单贪心。关键在于怎么最优,单纯的以时间或者食量排序是不行的,应该综合两者来考虑:假设有牛a和牛b:①如果先运输牛a再运输牛b:则破坏的花的数量为:2 * Ta * Db②如果先运输牛b再运输牛a:则破坏的花的数量为:2 * Tb * Da如果①<②:则 Ta * Db < Tb * Da#include<bits/stdc++.h>using namespace std;int n;struct node{


Protecting the Flowers

简单贪心。
关键在于怎么最优,单纯的以时间或者食量排序是不行的,应该综合两者来考虑:
假设有牛a和牛b:
①如果先运输牛a再运输牛b:则破坏的花的数量为:2 * Ta * Db
②如果先运输牛b再运输牛a:则破坏的花的数量为:2 * Tb * Da
如果①<②:
则 Ta * Db < Tb * Da

#include<bits/stdc++.h> using namespace std; int n; struct node{     long long t,d; }p[2000050]; bool cmp(node a,node b) {     return (a.d*1.0/a.t)>(b.d*1.0/b.t); } int main() {     cin>>n;     for(int i=0;i<n;i++)cin>>p[i].t>>p[i].d;     sort(p,p+n,cmp);     long long time=0,ans=0;     for(int i=0;i<n;i++)     {         ans+=time*p[i].d;         time+=2*p[i].t;     }     cout<<ans<<endl;       return 0; } 

c/c++开发分享Protecting the Flowers地址:https://blog.csdn.net/CesareBorgia/article/details/109646312

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/596830.html

(0)
上一篇 2021年5月8日
下一篇 2021年5月8日

精彩推荐