2023.6.21 每日一题

原题链接

A: Wunder Fund Round 2016 (Div. 1 + Div. 2 combined) - F

B: Codeforces Round 727 (Div. 2) - D

B. PriceFixed - 1600

题目大意

商店里有 \(n\) 个商品，价格为 \(2\)，至少要买第 \(i\) 件商品 \(a_i\) 个，同时如果我们总共买了超过 \(b_i\) 件商品，那么第 \(i\) 件商品打五折。问至少要花多少钱。

解题思路

直接贪心，将商品按照 \(b_i\) 从大到小排序。不考虑打折来买就是我们钱数的上界 \(2 \times n\)，我们考虑什么时候可以节省一部分钱，就是我们对一件商品花钱花到打折的时候，这件商品能打折并且总共花的钱少于我们不打折不多买花的钱。注意要按照我们对 \(b_i\) 排序的顺序，\(b_i\) 大的先考虑，才能保证贪心成立。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N = 4e5 + 10;
const int MOD = 1e9 + 7;

pair<LL, LL> p[N];
int idx[N];

bool cmp(int x, int y) {
    return p[x].second > p[y].second;
}

void solve() {
    int n;
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; ++i) {
        LL x, y;
        cin >> x >> y;
        p[i] = {x, y};
        sum += x;
        idx[i] = i;
    }
    sort(idx + 1, idx + n + 1, cmp);
    LL res = sum << 1;
    for (int i = 1; i <= n; ++i) {
        int id = idx[i];
        LL max_ = max(0ll, min(sum - p[id].second, p[id].first));
        res -= max_;
        sum -= max_;
    }
    cout << res << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}