题目链接

题意分析

首先如果当前序列中一头奶牛拿不到礼物的话

那么他后面的奶牛也拿不到礼物

所以我们可以二分

由于可以操作无限次

所以我们对于当前\([1,mid)\)的奶牛按照\(c\)值排序之后

贪心的先放\(c\)中最小的奶牛

如果依然存在一头奶牛被放在\(mid\)之前

那么就无法使\(mid\)得到礼物

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<string>

#include<queue>

#include<map>

#include<stack>

#include<list>

#include<set>

#include<deque>

#include<vector>

#include<ctime>

#define ll long long

#define inf 0x7fffffff

#define N 500008

#define IL inline

#define M 108611

#define D double

#define ull unsigned long long

#define R register

using namespace std;

template<typename T>IL void read(T &_)

{

    T __=0,___=1;char ____=getchar();

    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}

    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}

    _=___ ? __:-__;

}

/*-------------OI使我快乐-------------*/

int n,ans;

int num[M],tmp[M];

IL bool check(int mid)

{

	if(mid==1) return 1;

	for(R int i=1;i<mid;++i) tmp[i]=num[i];

	sort(tmp+1,tmp+mid);

	int now=n-mid;

	for(R int i=1;i<mid;++i)

	{

		if(tmp[i]>now) return 0;

		++now;

	}

	return 1;

}

int main()

{

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	read(n);

	for(R int i=1;i<=n;++i) read(num[i]);

	int le=1,ri=n;ans=-1;

	while(le<=ri)

	{

		int mid=(le+ri)>>1;

		if(check(mid)) le=mid+1,ans=mid;

		else ri=mid-1;

	}

	printf("%d\n",n-ans);

//	fclose(stdin);

//	fclose(stdout);

    return 0;

}

秒客网

P4090 [USACO17DEC]Greedy Gift Takers

题目链接

题意分析

CODE: