Atcoder Beginner Contest 415 D题

题目链接
题意: 给定 $N$ 个瓶子, $M$ 组交换策略. 对于每组交换策略: $A_i{B}_i$ , 用 $A_i$ 个瓶子换 $B_i$ 个瓶子, 并得到一个贴纸. 问: 最多可以获得多少个贴纸.

转换一下就是, 用 $N$ 个瓶子, 进行尽可能多的交换, 输出交换次数.

题解: 每交换一次, 减少的个数为: $A_i-B_i$ , 题目约束了 $A_i>B_i$ . 考虑交换的策略顺序, 自然是先交换减少的数量越少, 剩余的就越多, 也就是更优的.
所以可以对 $A_i-B_i$​ 升序排序.

排序之后, 依次遍历处理每一个交换策略. 对于任意一个交换策略 $AB$ , 设可以交换次数为 $k$. 要求交换 $k$ 次之后, 剩余的瓶子小于 $A$, 存在 $N-k\ast (A-B)<A$ => $k>\frac{N-A}{A-B}$ . 要求对于此次交换策略, 次数越大越优, 这个不等式求不出最大值. 考虑第 $k-1$ 次交换之后, 剩余的瓶子要求大于等于 $A$, 才能进行第 $k$ 次交换. 存在不等式 : $N-(k-1)\ast (A-B)\ge A$ => $k\le \frac{N-A}{A-B}+1$ , 此时 $k$ 的最大值为: $k_{max}=\lfloor \frac{N-A}{A-B}\rfloor +1$ . $A-B$ 表示每次交换之后损失的瓶子, $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;
}