0x05 排序

电影

莫斯科正在举办一个大型国际会议，有 个来自不同国家的科学家参会。
每个科学家都只懂得一种语言。
为了方便起见，我们把世界上的所有语言用 到 之间的整数编号。
在会议结束后，所有的科学家决定一起去看场电影放松一下。
他们去的电影院里一共有 部电影正在上映，每部电影的语音和字幕都采用不同的语言。
对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。
现在科学家们决定大家看同一场电影。
请你帮忙选择一部电影，可以让观影很开心的人最多。
如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。
输入格式
第一行输入一个整数 ，代表科学家的数量。
第二行输入 个整数 ，其中 表示第 个科学家懂得的语言的编号。
第三行输入一个整数 ，代表电影的数量。
第四行输入 个整数 ，其中 表示第 部电影的语音采用的语言的编号。
第五行输入 个整数 ，其中 表示第 部电影的字幕采用的语言的编号。
请注意对于同一部电影来说，。
同一行内数字用空格隔开。
输出格式
输出一个整数，代表最终选择的电影的编号。电影编号 。
如果答案不唯一，输出任意一个均可。
数据范围
,

输入样例：

3
2 3 2
2
3 2
2 3

输出样例：

2

map（红黑树，有序数据结构）/unordered_map（哈希，无序） 入门题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 200010;
int n, m, a[N], b[N], c[N];
unordered_map<int,int> mp;
// <key, value>
int main(){
  scanf("%d", &n);
  rep(i,1,n) scanf("%d", &a[i]), mp[a[i]] ++;
  scanf("%d", &m);
  rep(i,1,m) scanf("%d", &b[i]);
  rep(i,1,m) scanf("%d", &c[i]);
  int rs = 1;
  rep(i,2,m) {
    if(mp[b[i]] > mp[b[rs]]) {
      rs = i;
    } else if(mp[b[i]] == mp[b[rs]] && mp[c[i]] > mp[c[rs]]) {
      rs = i;
    }
  }
  printf("%d\n", rs);
  return 0;
}

货仓选址

在一条数轴上有 家商店，它们的坐标分别为 。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数 。
第二行 个整数 。
输出格式
输出一个整数，表示距离之和的最小值。
数据范围
,

输入样例：

4
6 2 9 1

输出样例：

12

最终选择的位置是中位数。证明如下：
排序后，第 i 个数左侧有 i 个，右侧有 n - i 个，如果有 n - i > i，那么答案应当在 i 右侧。因为从 i 往右移动一个单位距离，左侧 i 个位置距离都 +1，右侧 n - i 个距离都 -1，最终会使得答案变得更小。
当然可以选择排序后选择中位数，也可以使用 STL中的 nth_element 函数来保证数组的第 k 个数是排序后的第 k 个数（快速排序第 k 大的原理，复杂度O(n)，要比直接排序快很多。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 100010;
int n, a[N];
int main(){
  scanf("%d", &n);
  rep(i,1,n) scanf("%d", &a[i]);
  int k = (n + 1) / 2;
  nth_element(a + 1, a + k, a + 1 + n);
  ll sum = 0;
  rep(i,1,n) sum += abs(a[i] - a[k]);
  printf("%lld\n", sum);
  return 0;
}

七夕祭

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
于是 TYVJ 今年举办了一次线下七夕祭。
Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。
TYVJ 七夕祭和 11 区的夏祭的形式很像。
矩形的祭典会场由 排 列共计 个摊点组成。
虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。
Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。
不过 zhq 告诉 Vani，摊点已经随意布置完毕了，如果想满足 cl 的要求，唯一的调整方式就是交换两个相邻的摊点。
两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。
由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。
现在 Vani 想知道他的两个要求最多能满足多少个。
在此前提下，至少需要交换多少次摊点。
输入格式
第一行包含三个整数 和 和 ， 表示 cl 对多少个摊点感兴趣。
接下来 行，每行两个整数 ，表示 cl 对处在第 行第 列的摊点感兴趣。
输出格式
首先输出一个字符串。
如果能满足 Vani 的全部两个要求，输出 both；
如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多，输出 row；
如果只能使各列中 cl 感兴趣的摊点数一样多，输出 column；
如果均不能满足，输出 impossible。
如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。
数据范围
,
#card=math&code=0%20%5Cle%20T%20%5Cle%20min%28N%2AM%2C100000%29&id=uwutx),
,

输入样例：

2 3 4
1 3
2 1
2 2
2 3

输出样例：

row 1

首先判断 t 个能否平分到每行或每列。
对于每行的情况，求出每行应当有的个数
那么第 i 行需要挪动的个数为 ，令
易知 ，假设将第 i 行与第 i+1 行当做边界（不发生交换），那么每行需要挪动的个数依次为：

这个式子中的 可以消掉。由此可以化简为 「货仓选址」一题，选择中位数去计算答案即可。复杂度

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 100010;
int n, m, t, r[N], c[N];
ll rs;
void solve(int a[], int n, int ave) {
  int k = (n + 1) / 2;
  rep(i,1,n) {
    a[i] -= ave, a[i] += a[i-1];
  }
  nth_element(a + 1, a + k, a + n);
  rep(i,1,n) rs += abs(a[i] - a[k]);
}
int main(){
  scanf("%d%d%d", &n, &m, &t);
  rep(i,1,t){
    int x, y; scanf("%d%d", &x, &y);
    r[x] ++; c[y] ++;
  }
  int fg = 0;
  if(t % n == 0) {
    fg |= 1;
    solve(r, n, t / n);
  }
  if(t % m == 0) {
    fg |= 2;
    solve(c, m, t / m);
  }
  if(fg == 0) puts("impossible");
  else {
    if(fg == 3) printf("both");
    if(fg == 2) printf("column");
    if(fg == 1) printf("row");
    printf(" %lld\n", rs);
  }
}

动态中位数

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。
输入格式
第一行输入一个整数 ，代表后面数据集的个数，接下来若干行输入各个数据集。
每个数据集的第一行首先输入一个代表数据集的编号的整数。
然后输入一个整数 ，代表数据集中包含数据的个数， 一定为奇数，数据之间用空格隔开。
数据集的剩余行由数据集的数据构成，每行包含 个数据，最后一行数据量可能少于 个，数据之间用空格隔开。
输出格式
对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。
数据集的剩余行由输出的中位数构成，每行包含 个数据，最后一行数据量可能少于 个，数据之间用空格隔开。
输出中不应该存在空行。
数据范围
,
,
所有 相加之和不超过 。
输入样例：

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

用两个对顶堆维护即可。注意元素个数的及时调整。

#include <bits/stdc++.h>
using namespace std;
int T, t, n, x;
int main(){
    cin >> T;
    while(T--){
        cin >> t >> n;
        cout << t << ' ' << (n + 1) / 2 << endl;
        priority_queue<int> q;
        priority_queue<int, vector<int>, greater<int> > q2;
        int cnt = 0;
        for(int i=1;i<=n;i++){
            scanf("%d", &x);
            if(q.size() == 0 || x <= q.top())
                q.push(x);
            else q2.push(x);
            if(q.size() < q2.size()) {
                int x = q2.top(); q2.pop();
                q.push(x);
            }
            if(q.size() >= q2.size() + 2) {
                int x = q.top(); q.pop();
                q2.push(x);
            }
            if(i & 1) {
                printf("%d ", q.top());
                cnt ++;
                if(cnt % 10 == 0) puts("");
            }
        }
        if(cnt % 10) puts("");
    }
    return 0;
}

超快速排序

在这个问题中，您必须分析特定的排序算法——超快速排序。
该算法通过交换两个相邻的序列元素来处理 个不同整数的序列，直到序列按升序排序。
对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。
您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。
输入格式
输入包括一些测试用例。
每个测试用例的第一行输入整数 ，代表该用例中输入序列的长度。
接下来 行每行输入一个整数 ,代表用例中输入序列的具体数据，第 行的数据代表序列中第 个数。
当输入用例中包含的输入序列长度为 时，输入终止，该序列无需处理。
输出格式
对于每个需要处理的输入序列，输出一个整数 ，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。
数据范围
,
一个测试点中，所有 的和不超过 。

输入样例：

5
9
1
0
5
4
3
1
2
3
0

输出样例：

6
0

简单求逆序对

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 500010;
int n, a[N], b[N];
ll rs;
void merge(int l, int r) {
  if(l >= r) return;
  int mid = l + r >> 1; merge(l, mid); merge(mid + 1, r);
  int i = l, j = mid + 1, k = l;
  while(i <= mid && j <= r) {
    if(a[i] <= a[j]) {
      b[k++] = a[i++];
    }
    else {
      rs += mid - i + 1;
      b[k++] = a[j++];
    }
  }
  while(i <= mid) b[k++] = a[i++];
  while(j <= r) b[k++] = a[j++];
  rep(i,l,r) a[i] = b[i];
}
int main(){
  while(~scanf("%d", &n)){
    if(n == 0) break;
    rep(i,1,n) scanf("%d", &a[i]);
    rs = 0;
    merge(1, n);
    printf("%lld\n", rs);
  }
}

奇数码问题

你一定玩过八数码游戏，它实际上是在一个 的网格中进行的， 个空格和 这 个数字恰好不重不漏地分布在这 的网格中。
例如：

5 2 8
1 3 _
4 6 7

在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。
例如在上例中，空格可与左、上、下面的数字交换，分别变成：

5 2 8       5 2 _      5 2 8
1 _ 3       1 3 8      1 3 7
4 6 7       4 6 7      4 6 _

奇数码游戏是它的一个扩展，在一个 的网格中进行，其中 为奇数， 个空格和 这 个数恰好不重不漏地分布在 的网格中。
空格移动的规则与八数码游戏相同，实际上，八数码就是一个 的奇数码游戏。
现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

输入格式
多组数据，对于每组数据：
第 行输入一个整数 ， 为奇数。
接下来 行每行 个整数，表示第一个局面。
再接下来 行每行 个整数，表示第二个局面。
局面中每个整数都是 之一，其中用 代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

输出格式
对于每组数据，若两个局面可达，输出 TAK，否则输出 NIE。

数据范围

输入样例：

3
1 2 3
0 4 6
7 5 8
1 2 3
4 5 6
7 8 0
1
0
0

输出样例：

TAK
TAK

将局面按行列展开，得到 n*n-1 个数字，那么有一个结论：任意两个逆序对奇偶性相同的局面一定可以互相到达。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500*500+10;
ll num1,num2,n;
ll c[N];
void add(int x){
    for(;x<N;x+=x&-x)c[x]+=1;
}
ll ask(int x){
    ll num=0;
    for(;x;x-=x&-x)num+=c[x];
    return num;
}
int main(){
    while(~scanf("%d",&n)){
        num1=num2=0;
        memset(c,0,sizeof c);
        ll x;
        for(int i=1;i<=n*n;i++)
        {
            scanf("%lld",&x);
            if(x==0)continue;
            add(x);
            num1+=ask(x-1);
        }
        memset(c,0,sizeof c);
        for(int i=1;i<=n*n;i++)
        {
            scanf("%lld",&x);
            if(x==0)continue;
            add(x);
            num2+=ask(x-1);
        }
        if(num2%2==num1%2){
            printf("TAK\n");
        }
        else{
            printf("NIE\n");
        }
    }
    return 0;
}