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

description:

有M(M为偶数)头奶牛，每头奶牛有一个产奶量，将这些奶牛两两配对，每对奶牛的产奶的时间为两头奶牛产奶量的总和。现在这M/2对奶牛同时产奶，问所需的最短时间是多少 M保证为偶数

solution：

贪心。

将产奶量最少的和最多的匹配，最后取最大的时间即可

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct ben
{
    int x,y;
}a[100005];
bool cmp(ben s,ben t) 
{
    return s.y<t.y;
}
int main()
{
	int ans=0,n;
    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)
    {
    	ans=max(ans,a[i].y+a[j].y);
        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);
    return 0; 
}