题解 CF1593C Save More Mice
智子
2021-10-14 23:00:18
## 题意
在数轴上有一只猫，$k$ 只老鼠和一个洞，猫在点 $0$，洞在点 $n$，第 $i$ 只老鼠在点 $x_i (0 < x_i < n)$。
每个时刻有且仅有一只老鼠可以向右移动一位，猫也会向右移动一位。如果猫的位置和一只老鼠重合，猫就会吃掉这只老鼠，已经在洞的位置上的老鼠不会被吃掉。
求最多有多少只老鼠可以不被猫吃掉。
## 思路
这道题的解法是贪心。
现将所有老鼠按照坐标排序，再依次从第 $n$ 个老鼠开始，从右到左依次尝试将每一个老鼠移动到洞里，如果当前的老鼠已经被吃掉了就停止（所有老鼠已经不是到了洞里就是被吃掉）。
如果不移动最右侧的老鼠而是移动其他老鼠，最右侧老鼠不动而猫向右移动，猫与所有老鼠构成的区间长度缩短，答案显然不会更优。
## 代码
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 400000 + 5;
int a[MAXN];
int n, k;
int main() {
int T;
cin >> T;
while(T--) {
cin >> n >> k;
for(int i = 1; i <= k; i++) {
cin >> a[i];
}
sort(a + 1, a + k + 1);
int cat = 0, ans = 0;
for(int i = k; i >= 1; i--) {
if(cat >= a[i]) {
break;
}
int dis = n - a[i];
ans++;
cat += dis;
}
cout << ans << endl;
}
return 0;
}
```