[CF1141F2] Same Sum Blocks (Hard) - 贪心

Description

有一个序列 \(a_1,a_2,a_3...a_n (n\le 1500)\)，定义 \((l_i,r_i)=a[l_i] + a[l_i +1] +...+a[r_i]\)，找到最大的 \(k\) 使得 \((l_1,r_1)=...=(l_k,r_k)\) 且区间 \([l_1,r_1]...[l_k,r_k]\) 互不相交

Solution

很暴力的贪心问题

处理出每一个子串的和，记录为 \((l,r,sum)\) 的形式，将它们按照 \(sum\) 为第一关键字，\(r\) 为第二关键字排序

然后对于每一个 \(sum\) 相同的段内，经典贪心即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3000005;

int a[N],n,s[N],ind;

struct tup {
    int sum,l,r;
    bool operator < (const tup &b) {
        if(sum==b.sum) return r<b.r;
        else return sum<b.sum;
    }
} t[N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++) {
        for(int j=i;j<=n;j++) {
            t[++ind]={s[j]-s[i-1],i,j};
        }
    }
    sort(t+1,t+ind+1);
    int sum=0,ans=0,pos=0;
    vector <pair<int,int>> vec,vans;
    for(int i=1;i<=ind;i++) {
        if(t[i].sum!=t[i-1].sum) {
            ans=max(ans,sum);
            if(ans==sum) vans=vec;
            vec.clear();
            sum=0;
            pos=0;
        }
        if(t[i].l>pos) {
            ++sum;
            pos=t[i].r;
            vec.push_back({t[i].l,t[i].r});
        }
    }
    ans=max(ans,sum);
    if(ans==sum) vans=vec;
    cout<<ans<<endl;
    for(auto i:vans) cout<<i.first<<" "<<i.second<<endl;
}

[CF1141F2] Same Sum Blocks (Hard) - 贪心

原文：https://www.cnblogs.com/mollnn/p/12921741.html