AcWing 105. 七夕祭 原题链接
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
于是TYVJ今年举办了一次线下七夕祭。
Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。
TYVJ七夕祭和11区的夏祭的形式很像。
矩形的祭典会场由N排M列共计N×M个摊点组成。
虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。
Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。
不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。
两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。
由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。
现在Vani想知道他的两个要求最多能满足多少个。
在此前提下，至少需要交换多少次摊点。
输入格式
第一行包含三个整数N和M和T，T表示cl对多少个摊点感兴趣。
接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。
输出格式
首先输出一个字符串。
如果能满足Vani的全部两个要求，输出both；
如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；
如果只能使各列中cl感兴趣的摊点数一样多，输出column；
如果均不能满足，输出impossible。
如果输出的字符串不是impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。
数据范围
1≤N,M≤1000001≤N,M≤100000, 0≤T≤min(N∗M,100000)0≤T≤min(N∗M,100000), 1≤x≤N1≤x≤N, 1≤y≤M1≤y≤M
输入样例：
2 3 4
1 3
2 1
2 2
2 3
输出样例：
row 1
题目思路
static int[] row;
static int[] col;
private static long work(int n, int a[]) {
int[] sum = new int[n + 1];
int[] constant = new int[n + 1];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
if (sum[n] % n != 0) return -1;
int avg = sum[n] / n;
// c_i
constant[1] = 0;
for (int i = 2; i <= n; i++) constant[i] = sum[i - 1] - (i - 1) * avg;
Arrays.sort(constant, 1, n + 1);
long res = 0L;
int median = constant[(n + 1) / 2];
for (int i = 1; i < n + 1; i++) res += Math.abs(constant[i] - median);
return res;
}
public static void main(String[] args) {
int n = in.nextInt();
int m = in.nextInt();
int t = in.nextInt();
row = new int[n + 1];
col = new int[m + 1];
while (t-- > 0) {
row[in.nextInt()]++;
col[in.nextInt()]++;
}
long r = work(n, row);
long c = work(m, col);
if (r != -1 && c != -1) out.println("both " + (r + c));
else if (r != -1) out.println("row " + r);
else if (c != -1) out.println("column " + c);
else out.println("impossible");
out.flush();
out.close();
}
AcWing 106. 动态中位数 原题链接
依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。
输入格式
第一行输入一个整数PP，代表后面数据集的个数，接下来若干行输入各个数据集。
每个数据集的第一行首先输入一个代表数据集的编号的整数。
然后输入一个整数MM，代表数据集中包含数据的个数，MM一定为奇数，数据之间用空格隔开。
数据集的剩余行由数据集的数据构成，每行包含10个数据，最后一行数据量可能少于10个，数据之间用空格隔开。
输出格式
对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。
数据集的剩余行由输出的中位数构成，每行包含10个数据，最后一行数据量可能少于10个，数据之间用空格隔开。
输出中不应该存在空行。
数据范围
1≤P≤10001≤P≤1000, 1≤M≤99991≤M≤9999
输入样例：
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
输出样例：
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3
题目思路
使用对顶堆：小根堆的元素个数>=大根堆元素个数+1
private static class OxymoronHeap {
private PriorityQueue<Integer> less;
private PriorityQueue<Integer> large;
public OxymoronHeap() {
less = new PriorityQueue<>();
large = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
}
public void add(int x) {
if (less.isEmpty() || less.peek() <= x) {
less.add(x);
} else {
large.add(x);
}
if (less.size() > large.size() + 1) {
large.add(less.poll());
}
if (large.size() > less.size()) {
less.add(large.poll());
}
}
public int getMedian() {
return less.peek();
}
}
public static void main(String[] args) {
int t = in.nextInt();
while (t-- > 0) {
int number = in.nextInt();
int m = in.nextInt();
OxymoronHeap heap = new OxymoronHeap();
out.println(number + " " + ((m >> 1) + 1));
int count = 0;
for (int i = 1; i <= m; i++) {
heap.add(in.nextInt());
if ((i & 1) == 1) {
int median = heap.getMedian();
if (count >= 10) {
count = 0;
out.println();
}
out.print(median + " ");
count++;
}
}
out.println();
}
out.flush();
out.close();
}
AcWing 107. 超快速排序 原题链接
在这个问题中，您必须分析特定的排序算法—-超快速排序。
该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排序。
对于输入序列9 1 0 5 4，超快速排序生成输出0 1 4 5 9。
您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。
输入格式
输入包括一些测试用例。
每个测试用例的第一行输入整数n，代表该用例中输入序列的长度。
接下来n行每行输入一个整数aiai,代表用例中输入序列的具体数据，第i行的数据代表序列中第i个数。
当输入用例中包含的输入序列长度为0时，输入终止，该序列无需处理。
输出格式
对于每个需要处理的输入序列，输出一个整数op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。
数据范围
0≤N<5000000≤N<500000, 0≤ai≤9999999990≤ai≤999999999
输入样例：
5
9
1
0
5
4
3
1
2
3
0
输出样例：
6
0
static long res;
private static void countNumber(int[] arr, int[] temp, int start, int end) {
if (start >= end) return;
int mid = start + (end - start) / 2;
int l = start;
int r = mid + 1;
int idx = start;
countNumber(arr, temp, start, mid);
countNumber(arr, temp, mid + 1, end);
while (l <= mid && r <= end) {
if (arr[l] <= arr[r]) {
temp[idx++] = arr[l++];
} else {
res += mid - l + 1;
temp[idx++] = arr[r++];
}
}
while (l <= mid) temp[idx++] = arr[l++];
while (r <= end) temp[idx++] = arr[r++];
System.arraycopy(temp, start, arr, start, end - start + 1);
}
public static void main(String[] args) {
int n;
while ((n = in.nextInt()) != 0) {
int[] arr = new int[n];
in.nextIntegerArray(arr);
res = 0L;
countNumber(arr, new int[n], 0, n - 1);
out.println(res);
}
out.flush();
out.close();
}