题目 题意：给定长度为
n
n
n的数组
a
a
a和
k
k
k，其中
1
<
=
a
i
<
=
n
1<=a_i<=n
1<=ai<=n现在要求找出区间长度最小的
x
,
y
x,y
x,y，将数组
a
a
a划分成k个子数组，其中
a
i
a_i
ai位于这k个子数组的其中之一。要求每个子数组中，位于
[
x
,
y
]
[x,y]
[x,y]范围内的元素，多于不在
[
x
,
y
]
[x,y]
[x,y]范围内的元素。 现在构造出x,y，以及这k个子数组的区间。 官方题解 思路：考虑x,y已知的情况。对于每个
a
i
a_i
ai，如果
x
<
=
a
i
<
=
y
x<=a_i<=y
x<=ai<=y，则+1，否则记为-1。那么要求每个子数组累计得分要为正。因此，我们初始得分为0，当得分首次大于0时，则截取当前区间，并开始取新的区间，得分重新归零。注意最后一个区间（即第k个子数组）保留。这里用的是前缀和的思想。
如何确定x，y。不妨设上述得分数组为
b
b
b，前缀和数组为
p
r
e
pre
pre。我们可以发现
b
b
b取值为1，-1；从而
p
r
e
pre
pre相邻元素差值绝对值为1，即
∣
p
r
e
i
−
1
−
p
r
e
i
∣
=
1
|pre_{i-1}-pre_i|=1
∣prei−1−prei∣=1。要使按照上述贪心思路，能找到k组子数组，说明
p
r
e
n
pre_n
pren至少要有k，即
p
r
e
n
>
=
k
pre_n>=k
pren>=k；此外，由于
p
r
e
pre
pre是连续变化的，我们必然可以找到
p
r
e
pre
pre取值为1，2，…，k的下标，我们取它们出现的第一次位置即可。
要使
p
r
e
n
>
=
k
pre_n>=k
pren>=k，则有
2
∗
∑
i
=
1
n
[
x
<
=
a
i
<
=
y
]
−
n
>
=
k
2*\sum_{i=1}^{n}[x<=a_i<=y] - n>=k
2∗∑i=1n[x<=ai<=y]−n>=k，有
∑
i
=
1
n
[
x
<
=
a
i
<
=
y
]
>
=
⌈
n
+
k
2
⌉
\sum_{i=1}^{n}[x<=a_i<=y] >=\lceil \frac{n+k}{2}\rceil
∑i=1n[x<=ai<=y]>=⌈2n+k⌉ 我们可以对数组排序，枚举x从小到大，查看对应有
⌈
n
+
k
2
⌉
\lceil \frac{n+k}{2}\rceil
⌈2n+k⌉数量的y的最小取值，所有的情况中，取
y
−
x
y-x
y−x最小的。
官方代码，写的真好
#include
using namespace std;
int main() {
int tc;
cin >> tc;
while( tc-- ){
int n, k;
cin >> n >> k;
vector
for(int i=0; i cin >> a[i]; sorted_a[i] = a[i]; } sort(sorted_a.begin(),sorted_a.end()); int req_sum = ( n + k + 1 ) / 2; pair for(int i=0; i+req_sum-1 ans = min( ans , { sorted_a[i+req_sum-1] - sorted_a[i] , { sorted_a[i] , sorted_a[i+req_sum-1] } } ); cout << ans.second.first << ' ' << ans.second.second << '\n'; int subarrays_found = 0, curr_sum = 0; int last_uncovered = 1; for(int i=0; i if( a[i] >= ans.second.first && a[i] <= ans.second.second ) curr_sum ++; else curr_sum --; if( curr_sum > 0 && subarrays_found + 1 < k ){ cout << last_uncovered << ' ' << ( i + 1 ) << '\n'; last_uncovered = i + 2; subarrays_found ++; curr_sum = 0; } } subarrays_found ++; cout << last_uncovered << ' ' << n << '\n'; } return 0; }
发表评论