首页 > 代码库 > USACO 保护花朵 Protecting the Flowers, 2007 Jan
USACO 保护花朵 Protecting the Flowers, 2007 Jan
Description
约翰留下了 N 只奶牛呆在家里,自顾自地去干活了,这是非常失策的。他还在的时候,奶牛像 往常一样悠闲地在牧场里吃草。可是当他回来的时候,他看到了一幕惨剧:他的奶牛跑进了他的花园, 正在啃食他精心培育的花朵!约翰要立即采取行动,挨个把它们全部关回牛棚。 约翰牵走第 i 头奶牛需要 T i 分钟,因为要算来回时间,所以他实际需要 2 · T i 分钟。第 i 头奶牛 如果还在花园里逍遥,每分钟会啃食 Di 朵鲜花。但只要约翰抓住了它,开始牵走它的那刻开始,就 没法吃花了。请帮助约翰写一个程序来决定押送奶牛的顺序,使得花朵损失的数量最小。
Input Format
? 第一行:单个整数 N ,1 ≤ N ≤ 100000? 第二行到第 N + 1 行:第 i + 1 行有两个整数 T i 和 Di,2 ≤ T i ≤ 10 6 ; 1 ≤ Di ≤ 100
Output Format
? 单个整数:表示约翰损失的最小花朵数量
Sample Input
6 3 1 2 5 2 3 3 2 4 1 1 6
Sample Output
86
Hint
依次制服第六头,第二头,第三头,第四头, 第一头和第五头
Source
Protecting the Flowers, 2007 Jan
由题目可知对于 Ta Da Tb Db
只对后状态影响 设影响为w;则后状态为∑Di(max(a,b)+1<=i<=n)
若a排b前 w=Ta(∑Di+Db)+Tb*∑Di;
若b排a前 w=Tb(∑Di+Da)+Ta*∑Di;
消元后 发现 我们只要 对 Ta*Db<Tb*Da情况排序
然后模拟即可
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int i,j,k,l,m,n; long long ans,sum; struct st{int w,t;}mu[100010]; bool cmp(const st x,const st y) { if(x.t*y.w<y.t*x.w)return true; return false; } int main() { // freopen("xx.in","r",stdin); scanf("%d",&n); for(i=1;i<=n;sum+=mu[i].t*2,++i) scanf("%d%d",&mu[i].t,&mu[i].w); sort(mu+1,mu+n+1,cmp); long long num=sum; for(i=1;i<=n;++i) { ans+=(sum-num)*mu[i].w; num-=mu[i].t*2; } printf("%lld",ans); }
USACO 保护花朵 Protecting the Flowers, 2007 Jan
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。