大意: n个房间, 1为占用, 0为未占用, John要将k头奶牛和自己分进k+1个空房间, 求John距最远的奶牛距离的最小值

 

 

这种简单题卡了20min....

显然对于固定的k+1个房间, 只需要John在最接近中央的房间即可, 枚举每k个房间, 找出最接近的就行了

这样复杂度是$O(nlogk)$

还可以直接二分答案, 复杂度$O(nlogn)$

 

#include 
     
      #include 
      
       #include 
       
        #define REP(i,a,n) for(int i=a;i<=n;++i)using namespace std;const int N = 4e5+10;int n, k;int a[N];char s[N];int main() {	scanf("%d%d%s", &n, &k, s+1);	REP(i,1,n) if (s[i]=='0') a[++*a] = i;	n = *a;	int ans = 1e9;	REP(i,1,n-k) {		int j = i+k;		int p = lower_bound(a+i,a+j+1,(a[i]+a[j])/2)-a-1;		REP(r,p,p+3) if (i<=r&&r<=j) {			ans = min(ans, max(abs(a[i]-a[r]),abs(a[j]-a[r])));		}	}	printf("%d\n", ans);}