问AI才知道贪心错了，求估分 : (

第一次参加 NOIP 虽然知道难度超纲好多，当时以为要做出第一题好兴奋，唯独第六个样例是 83 我怎么做都是 82 就没管它，回来跑洛谷自测 100 分真的以为自己出息了（强省弱市里的蒟蒻孩儿），问了AI才发现贪心策略就不对，突然当头一棒呜呜呜。不知道 CCF 数据强度怎么样……不知道还有没有二三等奖。 ·悲哀·

CPP

#include <bits/stdc++.h>
#include <queue>
using namespace std;
typedef long long ll;

int main() {
    ll n, m, min_two = LONG_LONG_MAX, cnt = 0;
    cin >> n >> m;
    vector<pair<ll, ll>> vec(n + 1);
    vector<bool> sign(n + 1, false);
    for (ll i = 1; i <= n; i++) {
        cin >> vec[i].first >> vec[i].second;
        min_two = min(min_two, vec[i].first + vec[i].second);
    }
    for (ll i = 1; i <= n; i++) {
        if (vec[i].first * 2 <= min_two) {
            m -= vec[i].first;
            cnt++;
            sign[i] = true;
        }
    }

    cnt += m / min_two * 2;
    m %= min_two;

    priority_queue<ll, vector<ll>, greater<ll>> pq;

    for (ll i = 1; i <= n; i++) {
        if (!sign[i] && vec[i].first <= m) {
            // m -= vec[i].first;
            // cnt++;
            pq.push(vec[i].first);
        }
        if (sign[i] && vec[i].second <= m) {
            // m -= vec[i].second;
            // cnt++;
            pq.push(vec[i].second);
        }
    }

    while (!pq.empty() && m - pq.top() >= 0) {
        m -= pq.top();
        pq.pop();
        cnt++;
    }

    cout << cnt << endl;
}

问AI才知道贪心错了，求估分 : (

讨论操作

回复

相关推荐

问AI才知道贪心错了，求估分 : (