题解 P3669 【[USACO17OPEN]Paired Up 牛牛配对】

x_faraway_x · 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即可
}