$T1$ 电影

思路（卡常）：用map统计每个电影让多少人很开心，多少人较开心，最后排序即可。（关输入输出流可以直接卡常过）

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct P{
	int love,like,num;
};
const int N=2e5+50;
P a[N];
unordered_map<int,int> mp;
bool cmp(P a,P b){
	if(a.love==b.love) return a.like>b.like;
	return a.love>b.love;
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n;
	for(int i=1;i<=n;i++){
		int yy;
		cin >> yy;
		mp[yy]++;
	}
	cin >> m;
	for(int i=1;i<=m;i++){
		a[i].num=i;
	}
	for(int i=1;i<=m;i++){
		int yy;
		cin >> yy;
		a[i].love=mp[yy];
	}for(int i=1;i<=m;i++){
		int yy;
		cin >> yy;
		a[i].like=mp[yy];
	}
	sort(a+1,a+n+1,cmp);
	cout << a[1].num;
}

$T2$ 货仓选址

思路：选中间（偶数则看心情选一个），然后绝对值相加。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N];
signed main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	sort(a+1,a+n+1);
	int z=n/2+1,cnt=0;
	for(int i=1;i<=n;i++){
		if(i==z) continue;
		cnt+=abs(a[z]-a[i]);
	}
	cout << cnt;
}

$T3$ 七夕祭

思路：横竖均为环形均分纸牌问题，具体分析方法见小蓝书 (《算法竞赛进阶指南》) P37-39页。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+50;
int col[N],row[N];
int b[N];
int n,m,t;
int get(int n,int a[]){
    if(t%n) return 2e9;
    int pj=t/n,ans=0;
    for(int i=2;i<=n;i++){
        b[i]=b[i-1]+a[i]-pj;//换了一种形式写，本质不变
    }
    sort(b+1,b+n+1);
    int mid=(n+1)/2;
    for(int i=1;i<=n;i++) ans+=abs(b[mid]-b[i]);
    return ans;
}
signed main(){
    cin >> n >> m >> t;
    for(int i=1;i<=t;i++){
        int x,y;
        cin >> x >> y;
        row[x]++,col[y]++;
    }
    int a=get(n,row),b=get(m,col);
    if(a!=2e9&&b!=2e9) cout << "both " << a+b;
    else if(a!=2e9) cout << "row " << a;
    else if(b!=2e9) cout << "column " << b;
    else cout << "impossible"; 
}

$T4$ 动态中位数

思路：对顶堆

用两个堆，小根堆存储大的那一半数，大根堆存储小的那一半数。

每次插入时，通过和两个堆的堆顶比较确定进哪个堆，优先进大根堆（小的那一半），要输出时输出大根堆堆顶（也可以输出小根堆堆顶，但是要优先进小根堆）

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int t;
	cin >> t;
	while(t--){
		priority_queue<int> q;
		priority_queue<int,vector<int>,greater<int> > q2;
		int n,m;
		cin >> n >> m;
		cout << n << " " << (m+1)/2 << endl;
		int cnt=0;
		for(int i=1;i<=m;i++){
			int x;
			cin >> x;
			q2.push(x);
			if(q.size()&&q.top()>q2.top()){
				int a=q.top(),a2=q2.top();
				q.pop(),q2.pop();
				q2.push(a),q.push(a2);
			}
			if(q2.size()>q.size()+1){
				q.push(q2.top());
				q2.pop();
			}
			if(i%2==1){
				cout << q2.top() << " ";
				if(++cnt%10==0) cout << endl;
			}
		}
		if(cnt%10) cout << endl;
	}
}

$T5$ 超快速排序

思路：求逆序对原题

代码：有展示的必要吗？

$T6$ 奇数码问题

思路：

直接记性质吧：两个互通的奇数码局面，逆序对的奇偶性相同

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=503;
int q[N*N],q2[N*N],temp[N*N];
long long ans;
void merge_sort(int q[],int l,int r){
	if(l>=r) return;
	int mid=l+r>>1;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<=q[j]){
			temp[k]=q[i];
			k++;i++;
		}else{
			temp[k]=q[j];
			k++;j++;
			ans+=mid-i+1;
		}
	}
	while (i<=mid) temp[k++]=q[i++];
	while (j<=r) temp[k++]=q[j++];
	for(int i=l,j=0;i<=r;i++,j++){
		q[i]=temp[j];
	}
}
int main(){
	ios::sync_with_stdio(0);
//	cin.tie(0);
	cout.tie(0);
	int n;
	while(cin >> n){
		if(n==1){
			int a,b;
			cin >> a >> b;
			cout << "TAK\n";
			continue;
		}
		int f=0;
        for(int i=1;i<=n*n;i++){
        	int x;
            cin >> x;
            if(x==0) f=1;
            else q[i-f]=x;
        }
        f=0;
        for(int i=1;i<=n*n;i++){
        	int x;
            cin >> x;
            if(x==0) f=1;
            else q2[i-f]=x;
        }
		ans=0;
        for(int i=0;i<=N*N-1;i++){
        	temp[i]=0;
		}
        merge_sort(q,1,n*n-1);
        long long num1=ans;
        ans=0;
        for(int i=0;i<=N*N-1;i++){
        	temp[i]=0;
		}
        merge_sort(q2,1,n*n-1);
        long long num2=ans;
        ans=0;
        if((num1&1)==(num2&1)) cout << "TAK\n";
        else cout << "NIE\n";
	}
}

$T7$ 糖果传递

思路：和七夕祭一样，看小蓝书去。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000050],s[1000050],t,c[1000050];
int get(int n,int a[]){
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
	long long pj=t/n,ans=0;
	for(int i=1;i<=n;i++) c[i]=s[i-1]-(i-1)*pj;
	sort(c+1,c+n+1);
	int mid=(n+1)/2;
	for(int i=1;i<=n;i++) ans+=abs(c[mid]-c[i]);
	return ans;
}
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        t+=a[i];
    }
    cout << get(n,a);
}

$T8$ 士兵

思路：y轴直接货仓选址，x轴由于是站成一排，所以每个a[i]减去i。要记住，减完还要再排一次序

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+50;
int x[N],y[N],n;
signed main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> x[i] >> y[i];
	}
    sort(x+1,x+n+1);
    sort(y+1,y+n+1);
    for(int i=1;i<=n;i++){
        x[i]-=i-1;
    }
    sort(x+1,x+n+1);
    int mid=(n+1)/2,ans=0;
    for(int i=1;i<=n;i++){
        ans+=abs(x[i]-x[mid])+abs(y[i]-y[mid]);
    }
    cout << ans;
}