abc085d <贪心>-526互联

题目

思路

关键: 连续使用ai与投掷bi并无冲突, 可先使用ai再投掷bi
找到ai中的最大值maxa; 首先从大到小使用bi中比maxa大的元素, 而后不足h再重复使用maxa
(虽然按照先b后a的顺序分析计算, 但实际上应是先用a后用b)

代码

Code

// https://atcoder.jp/contests/abc085/tasks/abc085_d
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;
int a[N], b[N];

void solv()
{
    int n, h;
    cin >> n >> h;
    for (int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
    int maxa = *max_element(a+1, a+1+n);
    sort(b+1, b+1+n);
    LL sumb = 0, cntb = 0;
    for (int i = n; i >= 1; i --)
    {
        if (b[i] > maxa)
        {
            sumb += b[i];
            cntb ++;
            if (sumb >= h)
            {
                cout << cntb << endl;
                return;
            }
        }
        else break;
    }
    int ans = (h - sumb + maxa-1) / maxa + cntb;
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}