csp202303-2垦田计划

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn = 100005;
int n, m, k;
pair<int, int> o[maxn];
bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.first > b.first)
        return true;
    else if (a.first == b.first && a.second > b.second)
        return true;
    return false;
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &o[i].first, &o[i].second);
    }
    sort(o + 1, o + n + 1, cmp);
    while (1)
    {
        int s = o[1].first;
        int c = 0;
        for (int i = 1; i <= n; i++)
        {
            if (o[i].first == s)
            {
                c += o[i].second;
            }
            else
                break;
        }
        if (m > c)
        {
            m -= c;
            for (int i = 1; i <= n; i++)
            {
                if (o[i].first == s)
                {
                    o[i].first--;
                }
                else break;
            }
            // sort(o + 1, o + n + 1, cmp);
            // 这里不用再sort,因为每次t减后，仍然是从小到大的排列
        }
        else
        {
            cout << max(k, o[1].first);
            return 0;
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, m, k;
pair<int, int> tc[maxn];
bool cmp(pair<int, int> a1, pair<int, int> a2)
{
    if (a1.first > a2.first)
        return true;
    return false;
}
bool check(int t)//判断开垦天数为t时满不满足条件
{
    int sum=0;
    for(int i=0;i<n;i++){
        if(tc[i].first>t){//需要开垦
            sum+=(tc[i].first-t)*tc[i].second;
        }
    }
    if(sum>m){//可以开垦
        return true;
    }
    return false;
}
int main()
{
    cin >> n >> m >> k;
    int maxx = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> tc[i].first >> tc[i].second;
        maxx = max(maxx, tc[i].first);
    }//二分天数
    int l = k, r = maxx, mid = (l + r) / 2;
    while (l < r)
    {
        if (check(mid))
        {
            l = mid + 1;
        }
        else
            r = mid;
        mid = (l + r) / 2;
    }
    cout << mid;
}