题意:
给出n头牛的运输时间和每分钟的破坏值(如果该头牛没有被运走的话,每分钟造成的损失就是该破坏值);问将所有牛运送完造成的最小损失是多少。
解题思路:
我们先假设有两头牛i和j,两头牛的运送时间和破坏力为q[i].ti,q[i].val,q[j].ti,q[j].val;那么先运送i花费较小的前提是2 * q[i].ti * q[j].val<2 * q[j].ti * q[i].val -> q[i].ti * q[j].val<q[j].ti * q[i].val。所以我们可以对所有牛按照该表达式进行排序,然后从1到n贪心的运送即可。
代码如下:
#include<bits/stdc++.h> #define LL long long #define all(x) (x).begin(),(x).end() #define le(x) ((int)(x).size()) #define pii pair<int,int> #define PII pair<LL,LL> #define mp make_pair #define pb push_back #define fi first #define se second #define db printf("Here!\n"); using namespace std; const double eps=1e-8; const double Pi=4.0*atan(1.0); const LL inf=1e10+10; const int N=3e5+5; const int M=2e6+5; const int mod=1e9+7; int n,m,k,t,T,len,op,x,y,z,ok; struct node{ int ti,val; bool operator<(const node &p)const{ return ti*p.val<p.ti*val; } }q[N]; void solve(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&q[i].ti,&q[i].val); sort(q+1,q+1+n); LL ans=0,now=q[1].ti*2;//注意第一头牛不需要费用 for(int i=2;i<=n;i++){ ans+=now*q[i].val; now+=2*q[i].ti; } printf("%lld\n",ans); } int main(){ //int o;scanf("%d",&o); //while(o--){ solve(); //} return 0; }