A38 贪心算法

// 二分+贪心#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 100005
int n,c[N],b[N];

bool check(int mid){
  for(int i=1;i<mid;i++) b[i]=c[i];
  sort(b+1,b+mid); //贪心:为了尽可能让mid向前移
  
  int num=n-mid;   //mid后面一段的数量
  for(int i=1;i<mid;i++){
    if(b[i]<=num) num++; //插在mid后面，mid前移1位
    else return false;   //插在mid前面，mid不能前移
  }
  return true; //mid能到达队头
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++)scanf("%d",&c[i]);
  int l=0,r=n+1; 
  while(l+1<r){
    int mid=(l+r)>>1; //二分答案
    check(mid)?l=mid:r=mid;
  }
  printf("%d\n",n-l);
}

题目大意

• 第一个人插到从队尾数第 $c_i+1$ 的位置。

• 求不动的牛有多少个。

思路

显然的我们可以把这个序列分成两段，一段是循环，一段是完全不动的。

我们没有必要根据每个 $c_i$ 来实现 $O(n)$ 的算法，而且用字符串映射来去重加上链表，是一种很难实现的数据结构。

我们考虑二分最后一个动的牛即可。接下来就是 check 函数。

我们假设当前的牛是最后一个动的牛，则我们这一个牛一定能到达队头，否则这个就不是最后一个动的牛。

我们需要优化。

如果这个牛一定能到达队头，那么这头牛的前面的牛一定会把它往前面推。因为有些牛它会暂时阻碍这头牛的前进，时间复杂度会增加，我们需要每一头牛只做一次操作，可以进行一次排序？

• 排序不会影响结果。如果你要到后面你总会到后面的，还不如让可以直接到后面的先走一步，这样你也可以直接到后面。

• 排序可以直接判断合法性。如果这个插入后在你前面，那么后面的全部牛都会插入到前面，所以我们选的牛不会到队头。

最后时间复杂度 $O(n \log^2 n)$。

bool check(int x){
	int t[N];
	for(re int i=1;i<x;i++) t[i]=a[i];
	sort(t+1,t+x);
	
	int num=n-x;
	for(re int i=1;i<x;i++){
		if(t[i]<=num)
			num++;
		else
			return 0;
	}
	return 1;
}

[USACO] Greedy Gift Takers (P4090)

题目链接

// 二分+贪心
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 100005
int n,c[N],b[N];

bool check(int mid){
  for(int i=1;i<mid;i++) b[i]=c[i];
  sort(b+1,b+mid); //贪心:为了尽可能让mid向前移
  
  int num=n-mid;   //mid后面一段的数量
  for(int i=1;i<mid;i++){
    if(b[i]<=num) num++; //插在mid后面，mid前移1位
    else return false;   //插在mid前面，mid不能前移
  }
  return true; //mid能到达队头
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++)scanf("%d",&c[i]);
  int l=0,r=n+1; 
  while(l+1<r){
    int mid=(l+r)>>1; //二分答案
    check(mid)?l=mid:r=mid;
  }
  printf("%d\n",n-l);
}