题目传送门:P3669

题意解释

有 N 组牛，第 i 种牛有 x 个产量为 y 的牛，让他们两两分组后，使得产奶时间最少。

算法

这道题目是一道贪心题,适合像我这样的蒟蒻练习贪心。
对于贪心算法还不懂的蒟蒻可以看一看【百度百科】贪心算法哦！

思路

最小的时间与最长的时间进行配对，然后取他们的最大和。
配对完成后有以下几种情况：
- 最小与最大的时间刚好全部匹配结束了。
- 最小与最大中，只有最大的匹配结束了。
- 最小与最大中，只有最小的匹配结束了。
所以，我们需要先排序（建议不会快排的使用自带的快排函数），再贪心。

核心代码

    //在此以前为输入和排序!需要函数cmp和sturct的cow数组
    int Max=-1;
    for(int i=1,j=n;i<j;){
        if(cow[i].m==cow[j].m){
            Max=max(Max,cow[i].second+cow[j].second); 
            i++;j--;//首尾指针向内移动
        }else if(cow[i].m<cow[j].m){
            Max=max(Max,cow[i].second+cow[j].second);
            cow[j].m-=cow[i].m;//匹配完成要去掉,方便下一次计算
            i++;
        }else if(cow[i].m>cow[j].m){
            Max=max(Max,cow[i].second+cow[j].second);
            cow[i].m-=cow[j].m;//匹配完成要去掉,方便下一次计算
            j--;
        }
    }
    cout<<Max;//code by ZhanPJ

---

后记:

局部最优解与整体最优解：
1. 局部最优解：最大的产奶量与最小的产奶量进行一一匹配。
2. 整体最优解：按照从小到大排序后，再从最大产奶量与最小产奶量开始搜索，并一一匹配，匹配的时候再进行最大值的比较。