Problem - D - Codeforces

给定一个包含n个整数的数组a，找到一个值范围[æ， y] (z≤y)，并将a分割成恰好k(1≤k≤n)个子数组，如下所示:每个子数组由a的几个连续元素组成，即它等于a1, al+1，…， a，，对于某些l和r (1

Example

input

Copy

3

2 1

1 2

4 2

1 2 2 2

11 3

5 5 5 1 5 5 1 5 5 5 1

output

Copy

1 2
1 2
2 2
1 3
4 4
5 5
1 1
2 2
3 11

请注意在第一个测试中，应该只有一个子数组，它必须等于整个数组。在[1,2]范围内有2个元素，在[1,2]范围外有O个元素，如果选择的范围为[1,1)，则在(a1)范围内有1个元素，在(a2)范围外有1个元素，则答案无效。在第二个测试中，可以选择范围[2,2]，将数组拆分为子数组(1,3)和子数组(4,4)，在子数组(1,3)中有2个元素在范围内(a2和ag)和1个元素在范围外(a1)，在子数组(4,4)中只有1个元素(a4)，并且在范围内。在第三个测试中，可以选择范围[5,5)，并将数组拆分为子数组(1,4)，(5,7)和(8,11)，在子数组(1,4)中有3个元素在范围内和1个元素在外部，在子数组(5,7)中有2个元素在内部和1个元素在外部，在子数组(8,11)中有3个元素在内部和1个元素在外部。

题解:
假设cnt1为f(l,r)区间在(x,y)范围内的,cnt2为不在的,

f(l,mid) + f(mid+1,r) =  f(l,r) 如果f(l,r) > 0

那么f(l,r) == k是不是也可以由一个个小的区间f(l,r) == 1的区间合并过来呢

由于我们是求一个范围,我们先把数组里的数映射到一个数组上,记录哪个数出现几次,

如果要符合题意,应满足

cnt1 - cnt2 == k

cnt1 + cnt2 = n

cnt1 = (n + k) / 2

所以我们应该利用双指针,找到一个最小的,包含这么多数的区间,

找的区间后,输出即可

然后遍历数组,每次区间够1输出即可

#include
#include
#include
#include
#include
#include