Codeforces Round #547 (Div. 3) F2. Same Sum Blocks (Hard)
给定一个数列，求最多有多少个 不相交 并且 区间和相等 的区间。
首先枚举左右端点，然后将 n^2 个区间和相等的存到一起，按右端点的大小排序，然后考虑每一组和相等的，贪心选最多有多少个不相交的区间。
注意一定要按右端点来排序，如果按照左端点排序的话会错在第28个测试点，比如下面这组数据
6 5 4 -4 3 -3 -5如果左端点排序的话，他会直接将整个区间加入到sum=0的地方，但这显然是不对的，因为他中间包含了两个sum=0的区间，左端点排序一定取左端点，这样对右边可以会造成很大的影响，所以需要固定右端点来贪心选。
code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[1505], pre[1505];
map<int, int>value;
map<int, vector<pair<int, int> > >mp;
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
pre[i] = pre[i - 1] + a[i];
}
for (int i = 1; i <= n; i++)//右端点
{
for (int j = 1; j <= i; j++)//左端点
{
int temp = pre[i] - pre[j - 1];
if (value[temp] < j)
{
value[temp] = i;
mp[temp].push_back(pair<int, int>{j, i});
}
}
}
vector<pair<int, int> > ans;
for (auto it = mp.begin(); it != mp.end(); it++)
{
if (it->second.size() > ans.size())
ans = it->second;
}
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++)
printf("%d %d\n", ans[i].first, ans[i].second);
}
海康威视公司福利 1382人发布