多限制条件的处理

总结

介绍一种处理多限制条件时的解决方法，可以简单认为是通解

抽象来说，

当我们处理多限制条件时，假定为2个，选择固定其中一个条件，处理另一个条件

听起来是一个出于直觉的想法，但是这里我们采用相对策略的去考虑

具体一些，

类比一下中学的多动点问题，我们常见的解决方法是不是先固定一个点，看另一个点的移动情况？这样处理显然会更加简单

听起来很简单，但能第一时间想到并应用到题目中并不容易

可能有些抽象，我们结合题目来看…

例题

最优 K 子段

链接

Problem Description

给定一个序列 $a1,a2,…,an$，从中找出恰好 $k$ 个不相交的连续子段，满足每一段的长度都是质数。假设其中第 $i$ 个子段的子段和是 $s_i$，你需要最大化 $min(s1,s2,…,sk)$。

Input

每组数据第一行包含两个正整数 $n,k (2≤n≤200000, 1≤k≤n)$。

第二行包含 n 个整数 $a_1,a_2,…,a_n (|a_i|≤1000)$。

输入数据保证 $∑n≤10^6$，且每个 ai 都是在 $[−1000,1000]$ 均匀随机生成得到（样例除外）

分析

首先，需要最大化最小值，二分答案是显然的，以下介绍 check 内的部分

拆解一下，这里给出了两个限制条件，区间长度为质数，区间和不小于x

根据我们先前的策略，选择固定其中一个条件，处理另一个条件

在这里，质数这个条件较为固定（注意：我们这里说的固定，具体来说是指我们很难动态的去解决质数的变化，只能去简单的判断是否为质数，只能解决是不是的问题；但相反大小问题却很容易动态维护），

因此我们考虑固定质数这个条件，即把它当作那个固定的点，把大小这个条件当作移动的点进行维护，这样便可以处理了

如此操作，显然会便捷不少因为我们固定了质数这个条件，而大小变化则是易于处理的

Code

具体到代码，对于质数是不是的问题，我们可以通过素数筛预处理$O(1)$的解决

对于大小动态变化的问题，我们采取贪心的思想，利用$std::set$维护，只要对于当前这个区间满足是质数且大小不小于x，我们就立刻分割

遇到合法区间则立刻分割，我们会考虑枚举右端点

这样贪心的操作，一定可以分到最多的数量

本题的时间复杂度分析也是一难点，但是本文重在介绍这种处理方法，故略

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void SINGLE_TEST() 
{
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(2*k>n){
        cout<<"impossible\n";
        return;
    }
    vector<int> pr(n+1);
    for(int i=1;i<=n;i++){
        pr[i]=pr[i-1]+a[i];
    }
    auto check=[&](int x){
        set<pair<int,int>> se{{0,0}};
        int cnt=0;
        for(int i=1;i<=n;i++){
            bool ok=0;
            for(auto [v,p] : se){
                if(pr[i]-v<x) break;
                if(isp[i-p]){
                    ok=1;
                    break;
                }
            }
            if(ok){
                cnt++;
                se.clear();
            }
            se.emplace(pr[i],i);
        }
        return cnt>=k;
    };
    int l=-2000,r=2E8;
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid)){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    cout<<l<<"\n";
}