题意：给定n个奶牛，FJ把奶牛i从其位置送回牛棚并回到草坪要花费2*t[i]时间，同时留在草地上的奶牛j每分钟会消耗d[j]个草

        求把所有奶牛送回牛棚内，所消耗草的最小值

 

思路：贪心，假设奶牛a和奶牛b所处位置为，

　　　　交换前 ....(ta, da) (tb, db)....

　　　　交换后 ....(tb, db) (ta, da)....

 

设此前已消耗的时间为x，那么交换前消耗的草：x*da + (x+ta)*db

　　　　　　　　　　　　交换后消耗的草：x*db + (x+tb)*da

除非交换后的消耗相比交换前的小才交换，即ta*db > tb*da

 

AC代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 100005;const int INF = 0X3f3f3f3f;int n,t[N],d[N],sum,vis[N];struct node{	int t,d;}w[N];int cmp(node n1, node n2){	return n1.t*n2.d < n1.d * n2.t;}void solve(){	sort(w,w+n,cmp);	long long ans = 0;	for(int i = 0; i < n; i++)	{		sum -= w[i].d;		ans += sum*w[i].t*2;	}	cout<
         
          <