cf 2059B

//----------以下是主题内容------------------------------------------------- 这道题主要分为两种情况，一种是n=k，那么数组的分割方式就已经确定，那么只需按顺序找到b数组的最小成本即可。第二种是n>k，由于我们想找到b数组的最小成本，那么我们可以发现最小成本不会大于2，我们只需要在数组b的第一个区间去找最小成本即可。即a数组的第2-第n-k+2位置，如果这段区间所有数都为1，那么在第二个数就会得到b[2]！=2 ，最小成本就为2。如果有位置不为1，那么我们选此位置为b数组的起始位置就能得到b[1]！=1，最小成本就为1。

//--------以下是代码部分----------------------------------------------------

#include <algorithm>
#include <cmath>
#define ll long long
#define N 200005

using namespace std;

int n,k;
int a[N];

int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		if(n==k){
			int tot=1;
			for(int i=2;i<=n;i++){
				if(i%2==0){
					if(a[i]==tot) tot++;
					else{
						cout<<tot<<endl;
						break;
					}
				}
			}
			if(tot>n/2) cout<<tot<<endl;
		}
		else{
			int t=0;//记录b第一个区间1的数目
			for(int i=2;i<=n-k+2;i++){
				if(a[i]==1) t++;
			}
			if(t==n-k+1) cout<<2<<endl;
			else cout<<1<<endl;
		}
	}

	return 0;
}

//-----------以下是反思部分---------------------------------

1. 我们要找到最小成本，就用贪心思想在b的第一个区间上做文章，找到最小成本和第一个区间数的关联即可
2. 赛时猜想到第一个区间的特殊性，但是没有仔细研究，而是猜想dp解法放弃。