CF1593C Save More Mice(贪心&思维)题解

发布于 2021-10-21  40 次阅读


题目大意

$T$ 组数据。

坐标轴上有一只猫,$k$ 只老鼠和一个洞口。其中猫在坐标为 $0$ 的位置,洞口在坐标为 $n$ 的位置,并且给定每只老鼠的坐标 $x_i$。

在每一秒钟,我们可以选择一只老鼠向右走一个位置,如果一个老鼠到达洞口,它就通关了(不会再被吃掉)。在老鼠移动之后,猫会向右移动一个位置,并会吃掉它到达的位置上的老鼠(被吃掉的老鼠将不能再移动)。

持续以上过程直到所有的老鼠都已经隐藏起来或已经被吃掉。请你求出最多可以保护多少只老鼠通关。

$1 \le T \le 10^4$,$2 \le n \le 10^9$,$1 \le k \le 4 \times 10^5$,$1 \le x_i \le n$。

解题思路

首先,从贪心角度考虑,我们移动老鼠肯定是选中这只老鼠就一定会把它送到洞口(显然不送到洞口只是浪费步数)。

那么我们考虑现在选了 $k$ 只老鼠,可以发现一个结论:如果我们这 $k$ 只老鼠到洞口所需的步数之和小于猫到洞口的步数(也就是 $n-1$),那么我们一定可以把这 $k$ 只老鼠都送到洞口

为什么呢?我们考虑每次选离猫最近的那一只往后跑,由于我们花费的总步数大于猫的步数,那么我们一定保证每一只老鼠都可以安全到达洞口(可以把这个理解成一个动态调配的过程)。

这样的话,问题就转化为了选出最多的老鼠使得到洞口的总步数最小。而这个只需要把老鼠到洞的距离排序,从小到大取就好了。时间复杂度 $O(n \log n)$。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;

int n,k,a[N],b[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

signed main(){
    freopen("CF1593C.in","r",stdin);
    freopen("CF1593C.out","w",stdout);
    int T=read();
    while (T--){
        n=read(),k=read();
        for (int i=1;i<=k;++i) a[i]=read(),b[i]=n-a[i];
        sort(b+1,b+k+1);
        // printf("b: "); for (int i=1;i<=k;++i) printf("%lld ",b[i]); printf("\n");
        int rem=n-1,ans=0;
        for (int i=1;i<=k;++i){
            rem=rem-b[i];
            // printf("rem=%lld\n",rem);
            if (rem<0) break;
            ++ans;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

我们无法选择过去,但我们可以改变未来。