CF883I Photo Processing

题面

solution

硬是看出怎么 check 来，我是不是菜啊 = =

二分答案很显然。

考虑怎么 check

你排完序发现，它的权值是单调的，然后区间有必须选至少 (m) 个数。
然后你就可以用这两个限制条件来判断。

设 (dp_i) 表示到 (i) 点是否合法。

开个队列存一下对当前节点判断有效的节点，如果队列不为空，那么 (dp_i = 1)

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
int read() {
  int x = 0, f = 1; char c = getchar();
  while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
  while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  return x * f;
}
int n, m, a[MAXN], f[MAXN], Ans, q[MAXN];
bool Check(int x) {
  int head = 1, tail = 0;
  memset(f, 0, sizeof f);
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
  	if(i >= m && f[i - m]) q[++tail] = i - m;
  	while(head <= tail && a[i] - a[q[head] + 1] > x) head++;
  	if(head <= tail) f[i] = 1;
  }
  if(f[n]) return true;
  return false;
}
int main(){
  n = read(), m = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  sort(a + 1, a + n + 1);
  int l = 0, r = a[n] - a[1];
  while(l <= r) {
  	int mid = (l + r) >> 1;
  	if(Check(mid)) Ans = mid, r = mid - 1;
  	else l = mid + 1;
  }
  cout<<Ans;
  return 0;
}