Medians
https://vjudge.net/problem/CodeForces-2032B/origin
题目
给定一个数组 a=[1,2,…,n]a=[1,2,…,n]，其中 nn 是 奇数，以及一个整数 kk。
你的任务是选择一个 奇数 正整数 mm 并将 aa 分割成 mm 个子数组†† b1,b2,…,bmb1,b2,…,bm，使得：
- 数组 aa 的每个元素恰好属于一个子数组。
- 对于所有 1≤i≤m1≤i≤m，∣bi∣∣bi∣ 是 奇数，即每个子数组的长度为奇数。
- median([median(b1),median(b2),…,median(bm)])=kmedian([median(b1),median(b2),…,median(bm)])=k，即所有子数组的中位数数组的中位数‡‡ 必须等于 kk。median(c)median(c) 表示数组 cc 的中位数。
†† 数组 aa 的长度为 nn 的子数组是某些整数 1≤l≤r≤n1≤l≤r≤n 的数组 [al,al+1,…,ar][al,al+1,…,ar]。
‡‡ 奇数长度数组的中位数是数组按非递减顺序排序后中间的元素。例如： median([1,2,5,4,3])=3median([1,2,5,4,3])=3， median([3,2,1])=2median([3,2,1])=2， median([2,1,2,1,2,2,2])=2median([2,1,2,1,2,2,2])=2。
输入
每个测试由多个测试用例组成。第一行包含一个整数 tt (1≤t≤50001≤t≤5000) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 nn 和 kk (1≤k≤n<2⋅1051≤k≤n<2⋅105, nn 是 奇数) — 数组 aa 的长度和所有子数组的中位数数组的期望中位数。
保证所有测试用例的 nn 之和不超过 2⋅1052⋅105。
输出
对于每个测试用例：
- 如果没有合适的划分，输出 −1−1 在一行中。
- 否则，在第一行输出一个 奇数 整数 mm (1≤m≤n1≤m≤n)，在第二行输出 mm 个不同的整数 p1,p2,p3,…,pmp1,p2,p3,…,pm (1=p1<p2<p3<…<pm≤n1=p1<p2<p3<…<pm≤n) — 表示每个子数组的左边界。
具体来说，对于有效答案 [p1,p2,…,pm][p1,p2,…,pm]：
- b1=[ap1,ap1+1,…,ap2−1]b1=[ap1,ap1+1,…,ap2−1]
- b2=[ap2,ap2+1,…,ap3−1]b2=[ap2,ap2+1,…,ap3−1]
- ……
- bm=[apm,apm+1,…,an]bm=[apm,apm+1,…,an]。
如果有多个解，你可以输出其中任何一个。
示例
| Inputcopy | Outputcopy |
|---|---|
4 1 1 3 2 3 3 15 8 | 1 1 3 1 2 3 -1 5 1 4 7 10 13 |
注意
在第一个测试用例中，给定的划分有 m=1m=1 和 b1=[1]b1=[1]。显然 median([median([1])])=median([1])=1median([median([1])])=median([1])=1。
在第二个测试用例中，给定的划分有 m=3m=3 和：
- b1=[1]b1=[1]
- b2=[2]b2=[2]
- b3=[3]b3=[3]
因此，median([median([1]),median([2]),median([3])])=median([1,2,3])=2median([median([1]),median([2]),median([3])])=median([1,2,3])=2。
在第三个测试用例中，没有有效的划分满足 k=3k=3。
在第四个测试用例中，给定的划分有 m=5m=5 和：
- b1=[1,2,3]b1=[1,2,3]
- b2=[4,5,6]b2=[4,5,6]
- b3=[7,8,9]b3=[7,8,9]
- b4=[10,11,12]b4=[10,11,12]
- b5=[13,14,15]b5=[13,14,15]
因此，median([median([1,2,3]),median([4,5,6]),median([7,8,9]),median([10,11,12]),median([13,14,15])])=median([2,5,8,11,14])=8median([median([1,2,3]),median([4,5,6]),median([7,8,9]),median([10,11,12]),median([13,14,15])])=median([2,5,8,11,14])=8。
思路：
分三种情况：
1：k在端点，-1
2：k左右为偶数，5个区间
3：k左右为奇数，3个区间
（也可以又其他分法）
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int t, n, k;
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &k);
if (k == 1 && k == n) {
printf("1\n");
printf("1\n");
}
else if (k == 1 || k == n) {
printf("-1\n");
}
else if ((n - k) % 2 == 0) {
printf("5\n");
printf("%d %d %d %d %d\n", 1,k-1, k, k + 1,k+2);
}
else {
printf("3\n");
printf("%d %d %d\n", 1, k, k + 1);
}
}
return 0;
}