# 算法竞赛进阶指南-0x05基本算法-排序

Solution：

Code:

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n, m, numm;
int a[N], b[N], c[N], d[3 * N];
int ans[3 * N];

int find(int x){
return lower_bound(d + 1, d + numm + 1, x) - d;
}

int main(){
cin >> n;
int num = 0;
for(int i = 1; i <= n; i ++){
cin >> a[i];
d[++ num] = a[i];
}
cin >> m;
for(int i = 1; i <= m; i ++){
cin >> b[i];
d[++ num] = b[i];
}
for(int i = 1; i <= m; i ++){
cin >> c[i];
d[++ num] = c[i];
}
sort(d + 1, d + num + 1);
numm = unique(d + 1, d + num + 1) - (d + 1);
for(int i = 1; i <= n; i ++){
ans[find(a[i])] ++;
}
int x = 0, n1 = 0, n2 = 0;
for(int i = 1; i <= m; i ++){
int res1 = ans[find(b[i])];
int res2 = ans[find(c[i])];
if(res1 > n1 || (res1 == n1 && res2 > n2)){
x = i;
n1 = res1;
n2 = res2;
};
}
cout << x << endl;
return 0;
}


Solution：

n 为奇数时， 在 a[(n+1)/2] 处最优
n 为偶数时， 在 a[n/2]a[n/2+1] 处最优

Code:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;

int n;
int a[N];
ll ans = 0;

int main(){
cin >> n;
for(int i = 1 ; i <= n; i ++){
cin >> a[i];
}
sort(a + 1, a + n + 1);
int p;
if(n & 1)   p = a[(n + 1) / 2];
else    p = a[n / 2];
for(int i = 1; i <= n; i ++){
ans += abs(p - a[i]);
}
cout << ans << endl;
return 0;
}


Solution：

1-n 每个人有 a_1,a_2,a_3...a_n 个东西。
x_i 为第 i 个人给 i - 1 个人的东西数量。
avgna_i 的平均值

a_1 - x_1 + x_2 = a
a_2 - x_2 + x_3 = a
\cdot \cdot \cdot
a_{n-1} - x_{n-1} + x_n = a
a_{n} - x_n + x_1 = a

x_1=x_1-0
x_2=x_1-(a_1-a)
x_3=x_1-(a_1+a_2-2a)
\cdot \cdot \cdot
x_n=x_1-(a_1+a_2+\cdot \cdot \cdot + a_{n-1} - (n-1)a)

c_i 为上面式子等号右边。
ans=|x_1-c_1| + |x_1-c_2| + \cdot \cdot \cdot + |x_1-c_{n}|

Code:

#pragma GCC optimize(3,"Ofastx_1-c_1","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll row[N], col[N];
ll s[N], c[N];

ll fun(int n, ll a[]){
memset(s, 0, sizeof(s));
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; i ++)    s[i] = s[i - 1] + a[i];
ll avg = s[n] / n;
if(avg * n != s[n]) return -1;
for(int i = 2; i <= n; i ++)    c[i] = s[i - 1] - (i - 1) * avg;
ll res = 0;
sort(c + 1, c + n + 1);
for(int i = 1; i <= n; i ++)    res += abs(c[i] - c[(n + 1) / 2]);
return res;
}

int main(){
int n, m, cnt;
__;
cin >> n >> m >> cnt;
while(cnt --){
int x, y;
cin >> x >> y;
row[x] ++;
col[y] ++;
}
int r = fun(n, row);
int c = fun(m, col);
if(r != -1 && c != -1)  printf("both %lld\n", r + c);
else if(r != -1)    printf("row %lld\n", r);
else if(c != -1)    printf("column %lld\n", c);
else{
printf("impossible\n");
}
return 0;
}


Solution：

Code:

#include <bits/stdc++.h>
using namespace std;

int t, n, m, x;

int main(){
scanf("%d", &t);
while(t --){
scanf("%d%d", &m, &n);
priority_queue<int> down;
priority_queue<int, vector<int>, greater<int> > up;
int cnt = 0;
printf("%d %d\n", m, (n + 1) / 2);
for(int i = 1; i <= n; i ++){
scanf("%d", &x);
if(down.empty())    down.push(x);
else{
if(x < down.top())  down.push(x);
else up.push(x);
while(down.size() + 1 > up.size())
up.push(down.top()), down.pop();
while(up.size() > down.size())
down.push(up.top()), up.pop();
}
if(i & 1){
cnt ++;
printf("%d", down.top());
if(cnt % 10 == 0) putchar('\n');
else    putchar(' ');
}
}
if(cnt % 10)    putchar('\n');
}
return 0;
}


Solution：

Code:

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
typedef long long ll;

int n;
ll a[N], t[N];
ll ans;

void merge(int l, int r){
if(l >= r)   return ;
int mid = l + r >> 1;
merge(l, mid);
merge(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r){
if(a[i] < a[j]) t[k ++] = a[i ++];
else{
ans += mid - i + 1;
t[k ++] = a[j ++];
}
}
while(i <= mid) t[k ++] = a[i ++];
while(j <= r)   t[k ++] = a[j ++];
for(int i = l, j = 0; i <= r; i ++, j ++){
a[i] = t[j];
}
}

int main(){
while(~scanf("%d", &n)){
if(n == 0)  break;
ans = 0;
for(int i = 1; i <= n; i ++)    scanf("%lld", &a[i]);
merge(1, n);
printf("%lld\n", ans);
}
}


Solution：

Code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 250005;

int n, x;
int a[N], t[N];
ll ans1, ans2;

void merge(int l, int r, int f){
if(l >= r)  return ;
int mid = l + r >> 1;
merge(l, mid, f);
merge(mid + 1, r, f);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r){
if(a[i] <= a[j]){
t[k ++] = a[i ++];
}
else{
if(f)   ans1 += 1ll * mid - i + 1ll;
else    ans2 += 1ll * mid - i + 1ll;
t[k ++] = a[j ++];
}
}
while(i <= mid) t[k ++] = a[i ++];
while(j <= r) t[k ++] = a[j ++];
for(int i = l, j = 0; i <= r; i ++, j ++){
a[i] = t[j];
}
}

int main(){

while(~scanf("%d", &n)){
int num = 0;
ans1 = 0, ans2 = 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
scanf("%d", &x);
if(!x)  continue;
a[++ num] = x;
}
}
merge(1, num, 0);
num = 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
scanf("%d", &x);
if(!x)  continue;
a[++ num] = x;
}
}
merge(1, num, 1);
puts((ans1 & 1) == (ans2 & 1) ? "TAK" : "NIE");
}
return 0;
}