题目链接
题意: 给定 N N N 个瓶子, M M M 组交换策略. 对于每组交换策略: A i B i A_i B_i AiBi , 用 A i A_i Ai 个瓶子换 B i B_i Bi 个瓶子, 并得到一个贴纸. 问: 最多可以获得多少个贴纸.
转换一下就是, 用 N N N 个瓶子, 进行尽可能多的交换, 输出交换次数.
题解: 每交换一次, 减少的个数为: A i − B i A_i - B_i Ai−Bi , 题目约束了 A i > B i A_i > B_i Ai>Bi . 考虑交换的策略顺序, 自然是先交换减少的数量越少, 剩余的就越多, 也就是更优的.
所以可以对 A i − B i A_i - B_i Ai−Bi 升序排序.
排序之后, 依次遍历处理每一个交换策略. 对于任意一个交换策略 A B A\ B A B , 设可以交换次数为 k k k. 要求交换 k k k 次之后, 剩余的瓶子小于 A A A, 存在 N − k ∗ ( A − B ) < A N - k*(A-B)<A N−k∗(A−B)<A => k > N − A A − B k>\frac{N-A}{A-B} k>A−BN−A . 要求对于此次交换策略, 次数越大越优, 这个不等式求不出最大值. 考虑第 k − 1 k-1 k−1 次交换之后, 剩余的瓶子要求大于等于 A A A, 才能进行第 k k k 次交换. 存在不等式 : N − ( k − 1 ) ∗ ( A − B ) ≥ A N-(k-1)*(A-B)\ge A N−(k−1)∗(A−B)≥A => k ≤ N − A A − B + 1 k \leq \frac{N-A}{A-B}+1 k≤A−BN−A+1 , 此时 k k k 的最大值为: k m a x = ⌊ N − A A − B ⌋ + 1 k_{max} = \lfloor\frac{N-A}{A-B}\rfloor+1 kmax=⌊A−BN−A⌋+1 . A − B A-B A−B 表示每次交换之后损失的瓶子, N − A N-A N−A 表示可以损失的瓶子数. 仔细想一下, 上取整就不满足要求.
AC 代码如下:
#include <bits/stdc++.h>
#define _1 first
#define _2 second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
// 当减少的数量相等时, 不管先后, 总是能遍历到的.
bool cmp(PII a, PII b) {
return (a._1 - a._2) < (b._1 - b._2);
}
void slove()
{
LL n, m; cin >> n >> m;
vector<PII> a(m + 5);
for (int i = 1; i <= m; i++) {
cin >> a[i]._1 >> a[i]._2;
}
sort(a.begin() + 1, a.begin() + 1 + m, cmp);
LL res = 0;
for (int i = 1; i <= m; i++) {
LL x = a[i]._1, y = a[i]._2;
if (n >= x) {
LL cnt = (n - x) / (x - y) + 1; // 每个交换策略能交换的最大次数
res += cnt;
n -= cnt * (x - y); // 交换之后, 剩余的瓶子数量
}
}
cout << res << endl;
}