首页 > 代码库 > 洛谷 P2878 [USACO07JAN]保护花朵Protecting the Flowers 题解
洛谷 P2878 [USACO07JAN]保护花朵Protecting the Flowers 题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.luogu.org/problem/show?pid=2878
（本来想放bzoj的链接 然而bzoj这道题挂了）
【题目描述】
约翰留下他的N(N<=100000)只奶牛上山采木．他离开的时候，她们像往常一样悠闲地在草场里吃草．可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚． 牛们从1到N编号．第i只牛所在的位置距离牛棚Ti(1≤Ti≤2000000)分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食Di(1≤Di≤100)朵鲜花．无论多么努力，约翰一次只能送一只牛回棚．而运送第第i只牛事实上需要2Ti分钟，因为来回都需要时间． 写一个程序来决定约翰运送奶牛的顺序，使最终被吞食的花朵数量最小．
【输入格式】
第1行输入N，之后N行每行输入两个整数Ti和Di
【输出格式】
一个整数，表示最小数量的花朵被吞食
【样例输入】
6
3 1
2 5
2 3
3 2
4 1
1 6
【样例输出】
86
【样例解释】
约翰用6，2，3，4，1，5的顺序来运送他的奶牛
这题做的时候是hzwer神犇出的模考题，然后错得一塌糊涂qwq
分析：
这题用贪心来做。
单独看牛群中的两头牛a、b，每头牛拥有两个参数D和T。
假设这两头牛是相邻的，a在b之后被带走，考虑将这两头牛交换顺序，不会影响牛群中其他牛吃花的时间。
交换顺序前 吃花数量：2*T[b]*D[a]
交换顺序后 吃花数量：2*T[a]*D[b]
要使这次交换顺序是有效的，也就是说交换后的吃花数量减少了
则应满足 T[b]*D[a] > T[a]*D[b]
化简可得 D[a]/T[a] > D[b]/T[b]
推理可知，当一头牛的【吃花数量/带走时间】越大时，它应该先被带走。
简单理解的话也可以认为是先把腿长而且能吃的奶牛带走吧...（逃）
AC代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 7 using namespace std; 8 const int MAXN = 100005; 9 10 struct cow11 {12 int t,d;13 double jud;14 }a[MAXN];//存储奶牛的相关参数 15 16 long long sum[MAXN];17 18 bool cmp(cow a,cow b)19 {20 return a.jud > b.jud?1:0;21 }//根据比值来比较结构体大小 22 23 int main()24 {25 int n;26 scanf("%d",&n);27 for(int i = 0;i < n;++ i)28 {29 scanf("%d%d",&a[i].t,&a[i].d);30 a[i].jud = (double) a[i].d/a[i].t;31 }32 sort(a,a+n,cmp);33 34 sum[n-1] = (long long)a[n-1].d;35 for(int i = n-1;i >= 0;i --)36 sum[i] = (long long)a[i].d + sum[i+1];37 //计算剩余的i头奶牛每分钟吃掉的花朵 38 long long ans = 0;39 for(int i = 0;i < n;i ++)40 {41 ans += (long long)2 * a[i].t * sum[i+1];42 }43 printf("%lld",ans);44 return 0;45 }
大佬说最好用乘法，直观快速而且不用考虑精度。
……窝就是喜欢用除法嘛……窝就是觉得这样方便……
QAQ于是下面附上乘法的代码，@WZY大佬
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 inline void read(long long &x) 9 {10 x = 0;char ch = getchar();char c = ch;11 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();12 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar();13 if(c == ‘-‘)x = -x; 14 }15 const long long MAXN = 1000000 + 10;16 const int INF = 0x3f3f3f3f;17 18 long long n,T[MAXN],D[MAXN],cnt[MAXN];19 20 bool cmp(long long a, long long b)21 {22 return D[a] * T[b] > D[b] * T[a];23 }//直接根据乘法结果排序 24 25 long long ans;26 long long sum;27 28 int main()29 {30 // freopen("data.txt", "r", stdin);31 read(n);32 for(register long long i = 1;i <= n;++ i)33 {34 read(T[i]);read(D[i]);35 cnt[i] = i;36 sum += D[i];37 }38 std::sort(cnt + 1, cnt + 1 + n, cmp);39 for(register long long i = 1;i <= n;++ i)40 {41 sum -= D[cnt[i]];42 ans += ((long long)(sum * T[cnt[i]]) << 1);43 }44 printf("%lld", ans);45 return 0;46 }
或许这就是大佬吧
洛谷 P2878 [USACO07JAN]保护花朵Protecting the Flowers 题解