题号 NC25043
名称 Protecting the Flower
来源 USACO英文版-2007 January Contest-Silver

题目描述
Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport each cow back to its own barn.
Each cow i is at a location that is Ti minutes (1 ≤ Ti ≤ 2,000,000) away from its own barn. Furthermore, while waiting for transport, she destroys Di (1 ≤ Di ≤ 100) flowers per minute. No matter how hard he tries, FJ can only transport one cow at a time back to her barn. Moving cow i to its barn requires 2 × Ti minutes (Ti to get there and Ti to return). FJ starts at the flower patch, transports the cow to its barn, and then walks back to the flowers, taking no extra time to get to the next cow that needs transport.
Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.
输入描述:
Line 1: A single integer N
Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow's characteristics
输出描述:
Line 1: A single integer that is the minimum number of destroyed flowers
示例1
输入
复制
6
3 1
2 5
2 3
3 2
4 1
1 6
输出
复制
86

题意：
给你n头牛，要你搬运这n头牛，每次只能搬1头，给你出搬每头牛用的时间(单程)，再给出你每头牛每分钟破坏花数，问最小破坏多少花？

题解：知识点：贪心

贪心无非就是把这n头牛排一下序。
所以我们就要贪排序那个点，首先任意选这n头中相邻的两头牛A,B，他们的搬运时间分别是t1,t2。他们每分钟的破坏花数非别是d1,d2.我们设在A之前用过的时间是T。那么我们可以知道，无论是先A后B，还是先B后A，都不影响他们两个前面的时间，也不影响他们两个后面的时间，所以我们可以知道无论怎样都不影响前面的破坏花数。所以我们就要找A,B这两个谁先谁后更优。

如果A先B后：
花数：sum1=(Td1)+(T+t1)d2.
如果先B后A：
花数：sum2=(Td2)+(T+t2)d1.
比较这两个大小取最优就是
假设sum1<sum2即
(Td1)+(T+t1)d2 < (Td2)+(T+t2)*d1
T(d1+d2)+t1d2 < T(d1+d2)+t2d1
t1d2 < t2*d1
t1/d1 < t2/d2

t1/d1 < t2/d2
因为我们要最小，所以我们选择小的，即A先B后，即 图片说明 小的在前，大的在后，
或者图片说明 大的在前小的在后。

即排序按照 他俩的比值大小排序，这样会找到最优解。
排完序之后，要注意他是往返的，所以时间会是2倍。

图片说明代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

struct node {
    ll t,d;
    double bz;
}q[maxn];
bool cmp(node a,node b){
    return a.bz>b.bz;    
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>q[i].t>>q[i].d;
        q[i].bz=q[i].d*1.0/q[i].t;//平均的代价 
    }

    sort(q+1,q+1+n,cmp);

    for(int i=1;i<=n;i++)
    {
        sum+=q[i].d*t;//消耗时间乘代价 
        t+=q[i].t*2;//花费2倍的时间        
     } 
    pf("%lld\n",sum); 

    return 0;
}

图片说明 代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

struct node {
    ll t,d;
    double bz;
}q[maxn];
bool cmp(node a,node b){
    return a.bz<b.bz;    
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>q[i].t>>q[i].d;
        q[i].bz=q[i].t*1.0/q[i].d;//平均的代价 
    }

    sort(q+1,q+1+n,cmp);

    for(int i=1;i<=n;i++)
    {
        sum+=q[i].d*t;//消耗时间乘代价 
        t+=q[i].t*2;//花费2倍的时间        
     } 
    pf("%lld\n",sum); 

    return 0;
}