POJ 1989 The Cow Lineup

題意 :

農場主人請"牛"排成一row

想請問最小幾個數形成的數列 不能從牛序列取得子序列(可以不連續取得)

網路上的方法是用Greedy 

做法 : Greedy
參考作法 : http://www.acmerblog.com/hdu-2712-the-cow-lineup-4312.html

	#include<iostream>
	#include<cstdio>
	#include<cstring>
	using namespace std;
	int a[100001];//記錄牛隻編號
	bool visit[100001];//紀錄是否此數字已經有了!
	int main(){
	long int i,n,k,j,ans = 0;
	scanf("%d %d",&n,&k);//輸入牛的數目根編號範圍
	for(i=1;i<=n;i++)
	scanf("%d",&a[i]);//讀入牛的編號
	j = 0;
	memset(visit,false,sizeof(bool));//陣列初始化
	for(i=1;i<=n;i++){
	if(!visit[a[i]]){
	visit[a[i]] = true;
	j++;
	}
	if(j == k){
	for(int m=1;m<=n;m++){
	visit[m] = 0;
	}
	j = 0;
	ans++;
	}
	}
	printf("%d\n",ans+1);
	}

view raw gistfile1.cpp hosted with ❤ by GitHub