题意:
你在一个农场里面,农场里面有N头🐂,每头牛都有一个被牵回家的时间T和每分钟吃的草数量W,你赶牛回家的时间和来农场的时间相同,怎样安排牛回家的顺序使得,被吃的草数量最少。
思路:
- 一眼就是贪心,一般贪心要考虑排序或者优先队列,我们先考虑排序,首先W大的肯定是放在前面去拿走,W相同的时候肯定是优先选择T小的,那么这个优先级肯定是跟W和T有关。
- 我们考虑有这样两头牛A,B,谁应该先拿走呢?首先如果先拿走A,那么贡献就是A自身+B自身+2 * A.T * B.W,如果先拿走B,贡献就是A自身+B自身+2B.TA.W,小的肯定放前面啊,结构体排个序就行。
/* ▄███████▀▀▀▀▀▀███████▄ ░▐████▀▒▒▒▒▒▒▒▒▒▒▀██████▄ ░███▀▒▒▒ACCEPTED▒▒▒▒▀█████ ░▐██▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌ ░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌ ░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌ ░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌ ░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌ ░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌ ░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█ ░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀ ░░░░▄██████████████▒▒▐▌ ░░░▀███▀▀████▀█████▀▒▌ ░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐ ░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐ */ #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; const int INF=1e9+7; const int mod=998244353; typedef long long ll; typedef pair<ll,ll>pi; struct node { int t,w; bool operator<(const node &a)const { return t*2*a.w<a.t*w*2; } } a[N]; ll n,ans,now; int main() { cin>>n; for(int i=1; i<=n; i++) scanf("%d%d",&a[i].t,&a[i].w); sort(a+1,a+n+1); for(int i=1; i<=n; i++) { if(i==1) ans=ans+0,now=a[i].t*2; else ans=ans+a[i].w*now,now=now+a[i].t*2; } cout<<ans<<endl; } /* */