刷题记录:牛客NC24083Greedy Gift Takers

传送门:牛客

题目描述

Farmer John’s nemesis, Farmer Nhoj, has $N$ cows ($1\le N\le 10^5$), conveniently numbered $1\dots N$. They have unexpectedly turned up at Farmer John’s farm, so the unfailingly polite Farmer John is attempting to give them gifts.
To this end, Farmer John has brought out his infinite supply of gifts, and Nhoj’s cows have queued up in front of him, with cow $1$ at the head of the queue and cow $N$ at the tail. Farmer John was expecting that at every timestep, the cow at the head of the queue would take a gift from Farmer John and go to the tail of the queue. However, he has just realized that Nhoj’s cows are not that polite! After receiving her gift, each cow may not go to the tail of the queue, but rather may cut some number of cows at the tail, and insert herself in front of them. Specifically, cow $i$ will always cut exactly $c_i$ cows ($0\le c_i\le N-1$).
Farmer John knows that some cows might receive multiple gifts; as he has an infinite supply, this does not worry him. But he is worried that some cows might become unhappy if they do not get any gifts.
Help Farmer John find the number of cows who never receive any gifts, no matter how many gifts are handed out.

输入格式

The first line contains a single integer, $N$.
The second line contains $N$ space-separated integers $c_1,c_2,\dots ,c_N$.

输出格式

Please output the number of cows who cannot receive any gifts.

样例 #1

样例输入 #1

3
1 2 0

样例输出 #1

1

牛客网上的4星题,洛谷上曾经的紫题(现在也还是蓝题),可以说有一定的难度的,思考起来也比较费劲(虽然这道题的题面看起来并不复杂),大概花了我一个早上加中午的时间才完整的做出了这道题

主要思路;

1. 首先看完题目我们能够发现有以下一个现象,首先是他的转换操作是无限的(注意这一点,并不是一次的,而是可以一直的重复换牛的操作的),所以假设如果我们的标号为K的牛(下列简称为牛K)最终分不到自己的礼物的话,说明牛K之前的牛自己形成了一个循环,也就是永远都在牛K之前自己在反复领礼物,举个栗子,就如1,2,0这个栗子,操作一次形成2,1,0,在操作一次1,2,0发现又形成了之前的数列,永远都到不了牛0,也就是自己形成一个循环
2. 我们考虑思路一中的现象,然后思考一下,什么时候牛K之前的牛会自己形成一个循环呢,当然是牛K之前的数字无论怎样都到不了牛K之后的时候才会形成啦,换句话说,假设牛K之前的牛有机会都到达牛K之后的话,就说明牛K是能到达第一个的(也就是牛K之前并没有形成循环,也就是说牛K之前包括牛K都是可以领到礼物的),根据这个现象,我们就直接进行二分答案来找到最佳的牛K的位置(check函数我们在接下来会详细讲解)
3. 在思路二中我们发现可以用二分来解决这个问题,但是此时摆在我们面前的还有一个check函数,我们究竟该怎么办才能判断牛K之前的牛有没有构成一个循环了,在思路二中我们也提到了,如果牛K之前有一条牛无法到达牛K之后的话,就说明形成了一个循环,这时候肯定就有人会想了,这不是很简单吗,我直接循环一下不就解决了,但是注意,此时的移动并不是一次性的,题目中告诉了我们可以进行无数次的操作,所以并不能以上述那个朴素的想法去考虑这个问题

对于这个问题呢,我们试着将牛K之前的牛的Ci值进行排序操作,将其以(换之后插入的位置从大往小进行),为什么这么操作呢,这就是我们这篇题解中的重点了,因为我观看了各大的题解(包括洛谷和牛客),皆没有对这一步进行详细的解释,而我认为这一步恰恰是我们这道题的关键所在

我们试着想一下,因为我们的循环操作是无限次的,这说明了什么呢,说明我们无论有没有进行排序,即使我们是按照顺序进行操作的,也就是没有排序,但是依然是Ci值较大的先会到达牛K的后面,注意我们的操作是无限次的,也就是即使有一个牛之前第一次的操作没有到牛K之后,后来也依旧是有机会到牛K之后的,但是这就是在Ci值较大的之后在进行的事情了,也就是说此时我们考虑的是有哪些牛会达到牛K的后面,但是这个跟我们牛K之前的牛本来的排序其实是没有关系的,因为能出去的肯定会出去,无论早晚,不能出去的肯定是出不去的,如果还不能理解的话,可以试着结合下面我的证明来理解

对于一个数列,假设目前第一位为U,此时对于U有两种情况:A(U)>=k,此时U直接可以放到K之后假设此时的U是最大值,
那么这个和最大值先出去没有矛盾,假设它不是最大值,那么排在第一位的U都能出去,在U之后还比他大的数字肯定能
出去,与之前不矛盾
假设A(U)<=k,假设此时的U是最大值,那么之后的数字肯定是<=A(U)的,如果是等于的话之前无矛盾,如果是小于的话,那么至少也是减一,这个时候的话肯定还是出不去的,因为位置也相对减一了,所以形成了循环,也就是最大值出不去,就
形成循环,与之前不矛盾
假设此时的U不是最大值,那么此刻的U将会被换到后面等待下一次轮换,对于这种情况,我们的U进行换位置之后就会再
一次的重复我们上述的四种情况,假设有一次前三种,我们就不矛盾,假设一直都是第四种,那这是不可能的,因为迟早有
一次会换到最大的一个数,不然就是循环了,假设我们碰到了循环的情况的话(并且在循环形成之前最大值也没有碰到),那么我们最大值能不
能出去都对我们的判断没有造成影响,因为出去了,无伤大雅,因为本来也轮不到最大值,相当于减掉,如果没有出去,因为
本来我们就是循环的,所以也没有关系,直接判断为循环即可

下面是具体代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
int n,c[maxn];
bool cmp(int a,int b) {
	return a>b;
}
int fuzhu[maxn];
int check(int mid) {
	if(mid==1) return true;
	for(int i=0;i<mid;i++) fuzhu[i]=c[i];
	sort(fuzhu,fuzhu+mid,cmp);
	int kk=mid;
	for(int i=0;i<mid-1;i++) {
		if(fuzhu[i]<kk) {
			return false;
		}
		kk--;
	}              
	return true;
}
int main() {
	n=read();
	c[0]=-1;
	for(int i=1;i<=n;i++) {
		c[i]=read();
		c[i]=n-c[i];
	} 
	int l=0,r=n-1;int ans;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) {
			ans=mid;
			l=mid+1;	
		}else {
			r=mid-1;
		}
	}
	cout<<n-ans<<endl;
	return 0;
}