NC25043 Protecting the Flower（贪心）
Protecting the Flowers
https://ac.nowcoder.com/acm/problem/25043
题意
有n头奶牛跑到FJ的花园里去吃花儿了，它们分别在距离牛圈T分钟处吃花儿，每分钟会吃掉D朵卡哇伊的花儿，（此处有点拗口，不要在意细节啊！），FJ现在要将它们给弄回牛圈，但是他每次只能弄一头回去，来回用时总共为2*T分钟，在这段时间内，其它的奶牛会继续吃FJ卡哇伊的花儿，速度保持不变，当然正在被赶回牛圈的奶牛就没口福了！现在要求以一种最棒的方法来尽可能的减少花儿的损失数量，求奶牛吃掉花儿的最少朵数！
看完题目会发现这似乎和一道排队打水的题很想，只是加了一维而已，不难发现这是个贪心。
如何确定赶牛的顺序
对于两头牛 ,
在
前面当且仅当
所以以这个式子作为函数排序然后赶牛计算一下就行了
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
I int read() {
int s = 0 , w = 1; char ch = getchar();
while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
return s * w;
}
const int N = 1e6 + 5;
int n ,Ans;
struct node {
int T , D;
} a[N];
I bool cmp(node A , node B) {
return A.T * B.D < A.D * B.T;
}
signed main() {
n = read();
For(i , 1 , n) a[i].T = read() , a[i].D = read();
sort(a + 1 , a + n + 1 , cmp);
int sum = 0 ;
For(i , 1 , n) {
Ans += sum * a[i].D;
sum += 2 * a[i].T;
}
cout << Ans << endl;
return 0;
} 
学而思公司福利 626人发布
查看21道真题和解析