Codeforces Round #547 (Div. 3) F1/2. Same Sum Blocks (Easy/Hard) (贪心,模拟)

题意:有一长度为\(n\)的数组,求最多的区间和相同的不相交的区间的个数.
题解:我们可以先求一个前缀和,然后第一层循环遍历区间的右端点,第二层循环枚举左端点,用前缀和来\(O(1)\)求出区间和,\(pos\)表示当前区间和为\(cur\)的最右端点,如果我们枚举的左端点\(j\)比\(pos[cur]\)所在的最右端点大,那么我们就能得到区间和为\(cur\)的新区间,并更新状态.上面操作我们贪心得出一定是最优的.之后我们再遍历map,求出次数最多的区间和,然后再枚举所有区间,并且注意区间不能相交,所以我们需要记录所选区间的最右端点,每次都要使左端点大于最右端点,然后输出左右端点即可.

代码:

int n;

int a[N];

map<int,int> cnt;

map<int,int> pos;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n;

    rep(i,1,n){

    	cin>>a[i];

    	a[i]+=a[i-1];   //求前缀和

    }

    rep(i,1,n){

    	per(j,i,1){

    		int cur=a[i]-a[j-1];   //区间和

    		if(pos[cur]<j){

    			pos[cur]=i;   //更新某个区间和的右端点

    			cnt[cur]++;	  //统计贡献

    		}

    	}

    }

    int mx=0;

    int ans=0;

    for(auto w : cnt){

    	if(w.se>mx){

    		mx=w.se;

    		ans=w.fi;

    	}

    }

    cout<<cnt[ans]<<'\n';

    int rmx=0;

    rep(i,1,n){

    	per(j,i,1){

    		if(a[i]-a[j-1]==ans && j>rmx){  //注意区间不能相交

    			cout<<j<<' '<<i<<'\n';

    			rmx=i;

    		}

    	}

    }

    return 0;

}

巴特西

Codeforces Round #547 (Div. 3) F1/2. Same Sum Blocks (Easy/Hard) (贪心,模拟)

最新文章

热门文章