• 欢迎光临~

CF883I Photo Processing (二分,单调队列优化DP)

开发技术 开发技术 2022-06-22 次浏览

题意: 有一个n个数的集合,要分成若干子集,每个子集至少有m个数,每个子集的权值为最大数减最小数,求最小的最大权
思路: 先把数组排序。二分转化为判定性问题,check时候不能简单的贪心,设dp数组f[i]表示第i个数作为一个集合结尾是否可行 f[i] |= f[j] | l <= j <= r, 其中l是满足a[i] - a[l+1] < x的最小下标, i - r >= m. 所以这是个单调队列dp

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false) ,cin.tie(0), cout.tie(0);
//#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define PII pair<int, char>
//#define int long long
const int N = 3e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double PI = acos(-1.0);
int n, m;
int a[N]; bool f[N]; int q[N];
bool check( int x ) {
  f[0] = 1; int hh = 0, tt = -1;
  for ( int i = 1; i <= n; ++ i ) {
    if( i - m >= 0 && f[i - m] ) q[++tt] = i - m;
    while( hh <= tt && a[i] - a[q[hh] + 1] > x ) ++ hh;
    if( hh <= tt ) f[i] = 1;
  }
  bool ff = f[n];
  for ( int i = 1; i <= n; ++ i ) f[i] = 0;
  return ff;

}
void solve() {
  cin >> n >> m;
  for ( int i = 1; i <= n; ++ i ) cin >> a[i];
  sort(a + 1, a + 1 + n);
  int l = 0, r = 1e9;
  while( l < r ) {
    int mid = l + r >> 1;
    if( check(mid) ) r = mid;
    else l = mid + 1;  
  }
  cout << l << 'n';
}
int main() {
  IOS
  int t = 1; //cin >> t;
  while( t -- ) solve();
  return 0;
}
程序员灯塔
转载请注明原文链接:CF883I Photo Processing (二分,单调队列优化DP)
喜欢 (0)