FZU2216 The Longest Straight（思维 + 二分）

题目大意：给T组测试用例，首先有N和K分别表示n张牌以及牌的号码上限，接下来N个数表示牌号，问这N张牌能凑一个最长为多少的顺子，0表示癞子，每张都能够表示1 - K的任意一个号码。

思路：由于数据规模有1e5，很直观的思路就是枚举数字的起点和终点，复杂度 $O (n^{2})$ ，显然会超时。需要有一个log级的优化，我们将非癞子的数字排序，然后就可以利用二分搜索出终点，其中判断的条件是数列长度和癞子张数是否能够完美凑出起点到当前位置数字的长度。并且整个搜出来的长度的最大值不能超过K，全是癞子同理，需要在输出的时候来个判断。注意用GNU C++交的话用cin要关同步流，不然就全用scanf，还有就是自己写读入挂。否则会超时。

Code：

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
const int maxn = (int)1e5+5;

int T, N, flag, k;
int tab[maxn],vis[maxn];


int find(int l, int r, int start) {
	while (l < r) {
		int mid = (l + r) / 2;
		if (tab[mid] - tab[start] + 1 <= mid - start + 1 + flag) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	if (tab[l] - tab[start] + 1 <= l - start + 1 + flag) {
		return l - start + 1 + flag;
	}
	return l - start + flag;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int s;
	cin >> T;
	while (T--) {
		cin >> N >> k;
		memset(vis, 0, sizeof(vis));
		flag = 0; //癞子的个数 
		s = N;
		for (int i = 0; i < N; i++) {
			cin >> tab[i];
			if (!tab[i]) { //统计0的个数 
				flag++;
				i--;
				N--;
				continue;
			}
			if (!vis[tab[i]]) {
				vis[tab[i]] = 1;
			} else {
				i--;
				N--;
			}
		}
		if (N == 0) { //全都是癞子
			cout << (s > k ? k : s) << endl;
			continue;
		}
		sort(tab, tab + N);
		int Max = 0;
		for (int i = 0; i < N; i++) {
			Max = max(Max, find(i, N - 1, i));
		}
		cout << (Max > k ? k : Max) << endl;
	}
	return 0;
}