学步园

给一串数，数字的范围很大，但总个数N不大。现在允许最多抽走K个数字，问最多可以有多少个联通块（即为相同数字）。

一开始想到了DP，但是苦于推状态方程，并且有会超时的风险。后来又想到通过求逆序数，想了很久，才发现这样根本不对。。不如暴力枚举好了。。。

首先通过map离散化，然后开一个vector数组，记录每种数字出现的每个位置。

然后对这串数的每个位置开始枚举，向后查找能尽可能移多块的方案（在数串中的位置数的差 - 在vector中的位置数的差 = 中间的，多出了不同的数字的个数，即要移走的k），然后每次更新答案即可。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int maxn = 1e5 + 10;
int n, k;
int c[maxn],num[maxn];

map<int, int> m;
vector<int> que[100005];

int main()
{
//        freopen("C.in", "r", stdin);

        while(~scanf("%d%d", &n, &k))
        {
                for(int i = 0; i < n; i++)
                {
                        scanf("%d", &c[i]);
                        num[i] = c[i];
                }
                m.clear();
                sort(num, num + n);
                int mc = unique(num, num + n) - num;
                for(int i = 0; i < mc; i++)
                        m[num[i]] = i;
                for(int i = 0; i < mc; i++)
                        que[i].clear();
                for(int i = 0; i < n; i++)
                {
                    int id = m[c[i]];
                    que[id].push_back(i);
                }

                int ans = 0;
                for(int i = 0; i < mc; i++)
                {
                        int w = m[num[i]];
                        for(int st = 0; st < (que[w].size()); st++)
                        {
                                int L = st, R = que[w].size() - 1;
                                while(L <= R)
                                {
                                        int M = (L + R) >> 1;
                                        if (((que[w][M] - que[w][st] + 1) - (M - st + 1)) <= k)
                                        {
                                                ans = max(ans, M - st + 1);
                                                L = M + 1;
                                        }
                                        else
                                                R = M - 1;
                                }
                        }
                }

                printf("%d\n",ans);
    }
    return 0;
}

同样的做法，C++过了，但是Python跑T了，果然Python还是太慢啊，，，【ZOJ所有语言都一个时限真的好吗。。】

while True:
	try:
		m = {}
		n, k = map(int, raw_input().strip().split())
		c = map(int, raw_input().strip().split())
		ele = list(set(c))
		for i in range(len(ele)):
			m[ele[i]] = i
		que = [[] for i in range(len(ele))]
		for i in range(n):
			id = m[c[i]]
			que[id].append(i)
		ans = 0
		for i in range(len(ele)):
			w = m[ele[i]]
			for st in range(len(que[w])):
				l = st
				r = len(que[w]) - 1
				while(l <= r):
					mid = (l + r) / 2
					if((que[w][mid] - que[w][st] + 1) - (mid - st + 1) <= k):
						ans = max(ans, (mid - st + 1))
						l = mid + 1
					else:
						r = mid - 2
		print ans
	except EOFError:
		break