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

电影

题意:
蓝书P33

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;
}

货仓选址

题意:
蓝书P33

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;
}

七夕祭

题意:
蓝书P34

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=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}|
所以取 C 的中位数可使答案最小。

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;
}

动态中位数

题意:
蓝书P36

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;
}

超快速排序

题意:
蓝书P38

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);
    }
}

奇数码问题

题意:
蓝书P38

Solution:
结论:当 n 为奇数时,两个局面可达,当且仅当两个局面下网格中的数依次写成 1n \cdot n - 1 个元素后(不考虑空格),逆序对个数奇偶性相同。

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;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注