自动搬运

查看原文

来自洛谷，原作者为

	x_faraway_x 毫无特色的 OI 入门选手

搬运于2025-08-24 21:51:26，当前版本为作者最后更新于2017-03-20 18:28:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一题简单的贪心。

每次选产奶量最少的和产奶量最多的配对，取它们产奶时间的最大值就可以啦

具体见代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
struct Node
{
    int x, y;
}a[N];
bool cmp(Node s, Node t) //按照产奶量从大到小排序
{
    return s.y<t.y;
}
int n,ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,cmp);
    int i=1,j=n; //头尾指针分别指向产奶量最少的和产奶量最多的
    while(i<=j)
    {
        if(a[i].y+a[j].y>ans) ans=a[i].y+a[j].y; //产奶时间当前最长，更新答案ans
        if(a[i].x>a[j].x) //产奶少的奶牛数量大于产奶多的
        {
            a[i].x-=a[j].x; //产奶少的奶牛数量减去与产奶多的奶牛配对的数量
            j--; //修改尾指针
        } //下面同上不解释
        else if(a[i].x<a[j].x)
        {
            a[j].x-=a[i].x;
            i++;
        }
        else //产奶一样多，同时修改头尾指针
        {
            i++;
            j--;
        }
    }
    printf("%d",ans); //最后输出ans即可
}