题解 P4090 【[USACO17DEC]Greedy Gift Takers P】

QwQcOrZ · 2020-10-15 09:52:16 · 题解

显然如果一头牛拿不到礼物，那么他后面的牛也都拿不到礼物

那么就可以考虑二分第一个拿不到礼物的牛的位置，最后计算拿不到礼物的牛的个数并输出

如何 check 当前位置能否拿到礼物？考虑下述做法：

• 方便起见，我们称当前二分到的牛为 牛1437 ，设该牛的位置为 now
• 将当前位置之前的牛（即第 1 到第 now-1 头牛）按插入的位置从后到前排序（即降序排序）
• 将所有牛依次插入到其应该插入的位置（按之前排序的顺序），并改变 牛1437 的位置（now\gets now-1），如果插入到了 牛1437 的前面，那么 牛1437 就不可能获得礼物了，返回 \operatorname{false}
• 如果所有牛都插入到了 牛1437 的位置之后，说明此牛能拿到礼物，返回 \operatorname{true}

经过思考，我们会发现这个做法是对的

显然二分的 check 需要满足他是个充分必要条件，那么考虑证明此做法的充要性

先证明必要性：因为只有满足所有在 牛1437 前的牛都插入到 牛1437 之后了，牛1437 才能拿到礼物。而上述插入方式显然是最容易满足条件的，所以该条件有必要性

然后是充分性：显然当满足必要性的情况下，如果 牛1437 不能拿到礼物当且仅当 牛1437 之前的牛没有机会拿到礼物，以至于它不会插入到 牛1437 之后

而这种情况发生的唯一条件是 牛1437 之前的牛前面已经形成循环节了

又因为这题有单调性，也就是越前面的牛越容易合法。所以这里在 牛1437 之前的牛如果拿不到礼物，那么 牛1437 也拿不到礼物。如果由此迭代到第一个拿不到礼物的牛，就能发现在那个位置判也是不合法的（不能拿到礼物的）。而后面的牛显然不可能比前面的牛优（也就是更容易合法），所以 牛1437 也是不会合法的

故此有充分性

时间复杂度 O(nlog^2n)，用桶排可以优化到 O(nlogn)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;

int read()
{
    int s=0;
    char c=getchar(),lc='+';
    while (c<'0'||'9'<c) lc=c,c=getchar();
    while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
    return lc=='-'?-s:s;
}
void write(int x)
{
    if (x<0)
    {
        putchar('-');
        x=-x;
    }
    if (x<10) putchar(x+'0');
    else
    {
        write(x/10);
        putchar(x%10+'0');
    }
}
void print(int x,char c='\n')
{
    write(x);
    putchar(c);
}
int a[N],b[N],n;
bool check(int now)
{
    //因为题目给出的位置是从后往前数的，所以这里的位置都是以从最后一个向前的若干个的形式表示
    for (int i=1;i<now;i++) b[i]=a[i];
    sort(b+1,b+now);
    int tmp=n-now;//牛1437的位置
    for (int i=1;i<now;i++)
    {
        if (b[i]>tmp) return 0;
        tmp++;
    }
    return 1;
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    int l=1,r=n;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (check(mid)) l=mid+1;
                   else r=mid-1;
    }
    print(n-r);

    return 0;
}