Protecting the Flowers
题解:
感觉自己还是太年轻.....
这个题教会我一定要写数学式推导不然肯定WA
我们考虑一下两种取法:
- 先取a后取b
那么我们的消耗就是 - 先取b后取a
这时候的消耗就是
如果要满足先取a的方案是最优的,那需要满足,也就是
所以后面的思路就是排个序然后维护一下每一个奶牛等待时间的前缀和即可.
#define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> #define ll long long #define INF 0x3f3f3f3f #define inf -0x3f3f3f3f #define me(a,b) memset(a,b,sizeof(a)) #define PII pair<int,int> #define ull unsigned long long #define ios std :: ios :: sync_with_stdio(false) #define rep(i,a,b) for(int i = a;i <= b;i ++) #define esp 1e-16 #pragma war using namespace std; const int maxn = 1e5 + 18; struct Caw { int d, t; double rate; }a[maxn]; int n, sum[maxn]; bool cmd(Caw A, Caw B) { return A.rate < B.rate; } int main() { ios; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].t >> a[i].d; a[i].rate = (double)(1.0 * a[i].t / a[i].d); //cout << "rate = " << a[i].rate << endl; } sort(a + 1, a + 1 + n, cmd); ll ans = 0; sum[2] = a[1].t * 2; for (int i = 3; i <= n; i++) sum[i] += sum[i - 1] + a[i - 1].t * 2; //for (int i = 1; i <= n; i++) cout << sum[i] << endl; for (int i = 1; i <= n; i++) ans += sum[i] * a[i].d; cout << ans << endl; return 0; }