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); }

　　

轉載于:https://www.cnblogs.com/peter-le/p/6021175.html

總結

以上是生活随笔為你收集整理的USACO 保护花朵 Protecting the Flowers, 2007 Jan的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。