两年前的坑现在补上，经典的贪心+二分
#include <stdio.h> #include <string.h> const int maxn = 200005; int N,K,A,M; int pos[maxn]; bool vis[maxn]; bool judge(int m) { int i,cnt,len; memset( vis,false,sizeof(vis) ); for(i = 0; i < m; i++) vis[pos[i]] = true; cnt = 0; len = 0; for(i = 1; i <= N; i++) { if(vis[i]) { len = 0; continue; } len++; if(len == A) { cnt++; len = 0; i++; } } if(cnt >= K) return 0; else return 1; } int main(void) { int L,R,mid,ans,i; while(scanf("%d %d %d",&N,&K,&A) != EOF) { ans = -1; scanf("%d",&M); for(i = 0; i < M; i++) scanf("%d",&pos[i]); L = 1,R = M; while(L <= R) { //printf("%d %d %d\n",L,R,mid); mid = (L + R) >> 1; if(judge(mid)) { ans = mid; R = mid - 1; } else L = mid + 1; } printf("%d\n",ans); } return 0; }
