https://codeforces.com/contest/1141/problem/F2
题意
一个大小为 n 的数组 a[], 问最多有多少个不相交的区间和相等
题解
离散化用值来做, 贪心选择较前的区间
代码
- #include<bits/stdc++.h>
- #define M 5000005
- #define ll long long
- #define pb push_back
- using namespace std;
- struct N{int l,r;N(int l=0,int r=0):l(l),r(r){}};
- int n,i,j,p,ans,cnt,u,r,sz=0;
- ll a[2005],b[M];
- vector<N>g[M];
- int main(){
- cin>>n;
- for(i=1;i<=n;i++){
- scanf("%lld",&a[i]);a[i]+=a[i-1];
- for(j=i;j>=1;j--){
- b[sz++]=a[i]-a[j-1];
- }
- }
- sort(b,b+sz);sz=unique(b,b+sz)-b;
- for(i=1;i<=n;i++){
- for(j=1;j<=i;j++){
- p=lower_bound(b,b+sz,a[i]-a[j-1])-b;
- g[p].pb({j,i});
- }
- }
- ans=1;
- for(i=0;i<sz;i++){
- r=g[i][0].r;cnt=1;
- for(j=1;j<g[i].size();j++){
- if(g[i][j].l>r){
- cnt++;r=g[i][j].r;
- }
- }
- if(cnt>=ans){
- ans=cnt;u=i;
- }
- }
- printf("%d\n%d %d\n",ans,g[u][0].l,g[u][0].r);
- r=g[u][0].r;
- for(i=1;i<g[u].size();i++){
- if(g[u][i].l>r){
- printf("%d %d\n",g[u][i].l,g[u][i].r);
- r=g[u][i].r;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3005424.html