暴力解法 6 / 10

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
#define int long long
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;

priority_queue<PII> heap;

int a[N], b[N];

signed main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i];
        heap.push({a[i], i});
    }
    int ans = 0;
    for(int i = 1; i <= m; i ++)
    {
        if(heap.top().x <= 0) break;
        ans += heap.top().x;
        int id = heap.top().y;
        heap.pop();
        a[id] -= b[id];
        heap.push({a[id], id});
    }
    cout << ans << endl;
    return 0;
}

AC 解法

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N], b[N];

bool check(int mid)
{
    LL res = 0;
    for (int i = 0; i < n; i ++ )
        if (a[i] >= mid)
            res += (a[i] - mid) / b[i] + 1;
    return res >= m;
}

signed main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &a[i], &b[i]);

    int l = 0, r = 1e6;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    LL res = 0, cnt = 0;
    for (int i = 0; i < n; i ++ )
        if (a[i] >= r)
        {
            int c = (a[i] - r) / b[i] + 1;
            int end = a[i] - (c - 1) * b[i];
            cnt += c;
            res += (LL)(a[i] + end) * c / 2;
        }

    printf("%lld\n", res - (cnt - m) * r);
    return 0;
}