tuple解法

happybob · 2021-06-08 21:17:01 · 个人记录

一听到 tuple，你想到的肯定是 python，但是 c++11 也支持 tuple 这个类了，其实跟 struct 类似，但操作的函数会多一些。

用 tuple 做这道题也是需要贪心，我们先让这个人每天复习最大值，如果全部加起来还没有需要的大，那就直接 NO，不然的话做一个按照最大值减去最小值的排序（tuple 排序和数组是一样的，并没有迭代器 begin 和 end）。最后循环模拟一遍即可，但比较考代码能力。

代码：

#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;

int n;
const int N = 35;
tuple<int, int> tp[N], tp2[N];
int ans[N];
bool f[N];

bool cmp(tuple<int, int>& a, tuple<int, int>& b)
{
    return (get<1>(a) - get<0>(a) > get<1>(b) - get<0>(b));
}

void print()
{
    cout << "YES\n";
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int find(tuple<int, int>& a)
{
    for (int i = 1; i <= n; i++)
    {
        if (tp2[i] == a && !f[i])
        {
            f[i] = true;
            return i;
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    int sumTime, sum = 0;
    cin >> n >> sumTime;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        sum += y;
        get<0>(tp2[i]) = x;
        get<1>(tp2[i]) = y;
        ans[i] = y;
    }
    for (int i = 1; i <= n; i++) tp[i] = tp2[i];
    if (sum < sumTime)
    {
        cout << "NO\n";
        return 0;
    }
    if (sum == sumTime)
    {
        print();
        return 0;
    }
    sort(tp + 1, tp + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        int v = get<1>(tp[i]) - get<0>(tp[i]);
        if (sum - v > sumTime)
        {
            ans[find(tp[i])] = get<0>(tp[i]);
            sum -= v;
        }
        else if (sum - v == sumTime)
        {
            sum -= v;
            ans[find(tp[i])] = get<0>(tp[i]);
            print();
            return 0;
        }
        else if (sum - v < sumTime)
        {
            ans[find(tp[i])] = get<1>(tp[i]) - (sum - sumTime);
            print();
            return 0;
        }
    }
    cout << "NO\n";
    return 0;
}