标签：maxa abc085d int bi ai include sumb
题目
D - Katana Thrower
思路
- 关键: 连续使用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;
}
标签：maxa,
abc085d,
int,
bi,
ai,
include,
sumb
From： https://www.cnblogs.com/o2iginal/p/17555650.html