请求加入题解

本蒟蒻随便搓的贪心，看了看题解似乎没有和我思路一样的，有一位大佬是逆向思路跟我一样，但贪心的思路似乎有问题，这个方法简单又易于理解，以下是ai对我写法的概括

CF1764E 题解：逆向思维与动态贪心这道题初看之下，需要确定一个排列 p，情况非常复杂。但如果我们反过来思考，就能发现一条清晰的解题路径。一、核心思路：逆向思考我们的最终目标是用 1 号颜色染上点 k。根据规则，这有两种途径： k <= a_1：可以直接完成，输出 YES。 k > a_1：此时必须借助一个已经被染色的点 y，满足 y <= a_1 且 k <= y + b_1。对于第二种情况，条件可以转化为 k - b_1 <= y <= a_1。这意味着，我们需要在用 1 号颜色之前，用其他任意一个颜色（2 到 n 号），先染上一个坐标不小于 k - b_1 的点。至此，问题被巧妙地转化了：我们能否用 2...n 号颜色，实现“染上一个值至少为 T 的点”这个任务，其中初始目标 T = k - b_1？同时，我们也得到了两个简单的无解判断：若 k > a_1 + b_1，那么 k - b_1 > a_1，满足条件的 y 不存在，必为 NO。若初始时 a_1 >= k，直接满足条件，必为 YES。二、贪心策略：动态最优选择现在问题变成了如何用 2...n 号颜色达成目标 T。我们可以继续运用逆向思维。为了达成“染上点 T”这个目标，我们可以选择一个 i 号颜色（i > 1），借助它来降低问题的难度。如果我们使用 i 号颜色，问题就会变成一个更简单的子问题：“染上一个值至少为 T - b_i 的点”。那么，在什么时候我们可以用 i 号颜色来“降低难度”呢？当我们想从 T - b_i 拓展到 T 时，我们依赖的那个点（也就是 T-b_i）必须满足 T - b_i <= a_i，即 T <= a_i + b_i。所以，在任何一个时刻，对于当前的目标 T，所有满足 a_i + b_i >= T 的 i 号颜色，都成为了我们的“候选工具”。面对一堆“候选工具”，我们应该用哪个呢？为了让目标 T 下降得最快，从而让后续的子问题最简单、选择最多，我们显然应该选择那个 b_i 最大的工具。b_i 越大，T 下降得越多。三、算法实现基于以上分析，我们可以设计出如下算法：预处理：特判 k <= a_1 和 k > a_1 + b_1 的情况。然后，将 2...n 号的 (a_i, b_i) 数对存入一个数组，并按 a_i + b_i 的值从大到小排序。这一步是为了后续能快速地将满足条件的候选颜色加入选择范围。初始化：设定初始目标 targ = k - b_1。创建一个以 b_i 为第一优先级的最大优先队列（大根堆），用来存放所有可用的“候选工具”。主循环：首先，根据初始目标 targ，将排序后数组中所有满足 a_i + b_i >= targ 的颜色 i，将其 {b_i, a_i} 加入优先队列。当优先队列不为空时，循环执行：取出队首元素，即 b_i 最大的那个 {B, A}。成功判定：如果当前目标 targ 已经可以直接被这个颜色的 a_i 满足，即 A >= targ，说明我们已经找到了方法，直接输出 YES 并结束。降低目标：用这个最优工具降低目标，targ = targ - B。更新候选：因为目标 targ 变小了，可能会有更多颜色满足 a_i + b_i >= targ 的条件。从排序好的数组中，继续将满足新 targ 的颜色加入优先队列。失败判定：如果循环结束（优先队列为空），仍未找到解，则输出 NO。这个算法通过逆向思考将问题简化，并利用优先队列在每一步都做出最优的贪心选择，从而正确地解决了问题。

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
int X, Y, Z, n, m, u, k, Q, f, w, h;
#ifdef int
const long long inf = LLONG_MAX >> 4;
#else
const int inf = 0x3f3f3f3f;
#endif
#define FASTER ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
#define vec(a, n) vector<int> a(n + 1, 0)
#define veci(a, n) vector<int> a(n + 1, inf)
#define vecvec(a, i, j, ini) vector<vector<int>> a(i + 1, vector<int>(j + 1, ini))
#define vecin(a, n)              \
    vector<int> a(n + 1);        \
    for (int i = 1; i <= n; i++) \
        cin >> a[i];
#define strcin(x) \
    string x;     \
    cin >> x;     \
    x = ' ' + x;  \
    n = x.size() - 1;
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define debug(x) cerr << #x << " = " << x << "\n"
#define debug2(x, y) cerr << #x << " = " << x << "  " << #y << " = " << y << "\n"
const int mod = 998244353;
const int maxn = 1e5 + 100;
void solve()
{
    cin >> n >> k;
    vec(a, n);
    vec(b, n);
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    vector<array<int, 3>> c(n + 1);
    for (int i = 1; i <= n; i++)
        c[i] = {a[i] + b[i], a[i], b[i]};
    sort(c.begin() + 2, c.end(), greater<array<int, 3>>());
    int loc = 2;
    if (a[1] >= k)
    {
        cout << "YES" << endl;
        return;
    }
    if (b[1] + a[1] < k)
    {
        cout << "NO" << endl;
        return;
    }
    int targ = k;
    priority_queue<pair<int, int>> q;
    q.push({b[1], a[1]});
    while (q.size())
    {
        auto [B, A] = q.top();
        q.pop();
        if (A >= targ)
        {
            cout << "YES" << endl;
            return;
        }
        int newtarg = targ - B;
        for (; c[loc][0] >= newtarg && loc <= n; loc++)
        {
            q.push({c[loc][2], c[loc][1]});
        }
        targ = newtarg;
    }
    cout << "NO" << endl;
}
signed main(void)
{
    FASTER
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

讨论操作

回复

相关推荐

请求加入题解