USACO备考冲刺必刷题 | P3669 Paired Up

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

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

【输入】

第一行为一个正整数N

接下来有N行，每行两个正整数x和y，表示有x头奶牛的产奶量为y。保证所有x的总和等于M

【输出】

输出产奶时间的最小值

【输入样例】

3
1 8
2 5
1 2

【输出样例】

10

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n;
long long ans=-1e9;
struct node {
    int cnt, v;
}p[100005];
bool cmp (node a, node b)
{
    return a.v < b.v;
}
int main()
{
    cin >> n;  // 输入n
    for (int i=1; i<=n; i++) {  // 遍历n组数据
        cin >> p[i].cnt >> p[i].v;  // 记录每组的奶牛数和奶牛产奶量
    }
    sort(p+1, p+n+1, cmp);  // 按照产奶量从小到大排序
    int i=1, j=n;  // 定义双指针，分别指向头和尾
    while (i<=j) {  // 双指针模板
        ans = max(ans, 1ll*(p[i].v+p[j].v));  // 计算最大值（所有奶牛同时产奶，最短时间就是总和的最大值）
        if (p[i].cnt>p[j].cnt) {  // 如果i的数量大于j的数量
            p[i].cnt = p[i].cnt - p[j].cnt;  // 得到i的剩余数量，用于下次配对
            p[j].cnt = 0;  // j的数量修改为0（其实不改也行）
            j--;  // j向前移动
        } else if (p[i].cnt<p[j].cnt) {  // 如果j的数量大于i的数量
            p[j].cnt = p[j].cnt - p[i].cnt;  // 得到j的剩余数量，用于下次配对
            p[i].cnt = 0;  // i的数量修改为0（其实不改也行）
            i++;  // i向后移动
        } else {  // 否则（两者相等）
            i++;  // i向后移动
            j--;  // j向前移动
        }
    }
    cout << ans << endl;  // 输出结果
    return 0;
}

【运行结果】

3
1 8
2 5
1 2
10