《算法竞赛进阶指南》 0x05 ~ 0x06 代码 + 杂谈

排序

离散化

例题 Cinema
之前一直读错题 orz 今天补下

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 5;

int a[maxn], b[maxn], num[maxn];
struct node{
    int id;
    int lan;
    int sub;
    bool operator < (const node & a) const {
        return a.lan < lan || (a.lan == lan && a.sub < sub);
    }
}mo[maxn];

int chk(int x, int cnt){
    int l = 1, r = cnt;
    while(l < r) {
        int mid = l + r >> 1;
        if(b[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if(x != b[l]) return 0;
    else return l;
}

int main(){
    int n, m;
    cin >> n;
    for(int i = 1, t; i <= n; i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i ++ ) 
        num[chk(a[i], n)] ++;
    cin >> m;
    for(int i = 1, pos; i <= m; i ++ ) {
        cin >> pos;
        mo[i].id = i;
        pos = chk(pos, n);
        pos ? mo[i].lan = num[pos] : 0;
    }
    for(int i = 1, pos; i <= m; i ++ ) {
        cin >> pos;
        pos = chk(pos, n);
        pos ? mo[i].sub = num[pos] : 0;
    }
    sort(mo + 1, mo + 1 + m);
    cout << mo[1].id << endl;
    return 0;
}

货仓选址问题
ps 一般固定点选中位数 如果 没有这个要求的话 那个平均数更好

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5 ;
int n, m, a[maxn];

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

七夕祭
这题和货舱选址 用中位数 并且 和 均分纸牌有关
首先我们 先想 对一个列 or 行 进行纸牌均分 而且他是成环的 我们可以考虑从k人隔开
为了让这个和最小 我们最好 选中位数(货舱选址) 所以这题就这样狗出来了

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 100000 + 5;

int N, M, T;
int c[2][maxn], a[maxn], s[maxn];

int main(){
    cin >> N >> M >> T;
    for(int i = 1; i <= T; i ++ ) {
        int x, y;
        cin >> x >> y;
        c[0][y] ++;
        c[1][x] ++;
    }
    if((T % N) != 0 && (T % M) != 0) {
        cout << "impossible" << endl;
        return 0;
    }
    int ans = 0, flag = 0, ok = 0;
    if((T % M) == 0){
        int TM = T / M;
        for(int i = 1; i <= M; i ++ ) {
            a[i] = c[0][i] - TM;
            s[i] = s[i - 1] + a[i];
        }
        sort(s + 1, s + 1 + M);
        int mid = s[M + 1 >> 1];
        for(int i = 1; i <= M; i ++ ) {
            ans += abs(s[i] - mid);
        }
        ok = 1;
    }
    if((T % N) == 0){
        int TM = T / N;
        for(int i = 1; i <= N; i ++ ) {
            a[i] = c[1][i] - TM;
            s[i] = s[i - 1] + a[i];
        }
        sort(s + 1, s + 1 + N);
        int mid = s[N + 1 >> 1];
        for(int i = 1; i <= N; i ++ ) {
            ans += abs(s[i] - mid);
        }
        flag = 1;
    }
    if(flag && ok) cout << "both " << ans << endl;
    else if(flag) cout << "row " << ans << endl;
    else cout << "column " << ans << endl;
    return 0;
}

动态中位数 对顶堆 我记得我以前那权值线段树水过一个各种中位数的题
开两个堆，一个大根堆，一个小根堆，大根堆用来存放已经扫描到的元素里面，从小到大排名为前一半的元素，小根堆放后一半比较大的数　每次查询小根堆堆顶即为中位数。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e5 + 5 ;
int n, m;

priority_queue<int, vector<int>, greater<int> > minheap;
priority_queue<int, vector<int>, less<int> > maxheap;

int main() {
    int cas;
    cin >> cas;
    while(cas --) {
        while(!minheap.empty()) minheap.pop();
        while(!maxheap.empty()) maxheap.pop();
        cin >> m >> n;
        cout << m << " " << (n + 1) / 2 << endl;

        for(int i = 1, t; i <= n; i ++ ) {
            cin >> t;
            if(minheap.empty()) minheap.push(t);
            else if(minheap.top() < t) minheap.push(t);
            else maxheap.push(t);

            if(minheap.size() < maxheap.size()) minheap.push(maxheap.top()), maxheap.pop();
            else if(minheap.size() > maxheap.size() + 1) maxheap.push(minheap.top()), minheap.pop();

            if(i & 1) cout << minheap.top() << " ";
            if(i % 20 == 0) cout << endl;
        }
        cout << endl;
    }
    return 0;
}

ｋ大数

#include <iostream>
using namespace std;
int n, a[500], k, ans, f;
int qsort(int left, int right) {
    if(left == right) return a[left];
    if(left > right) return 0;
    int l = left, r = right;
    int x = a[l];
    while(l < r) {
        while(l < r && a[r] < x) r--;
        if(l < r) a[l++] = a[r];
        while(l < r && a[l] > x) l++;
        if(l < r) a[r--] = a[l];
    }
    a[l] = x;
    if(l == k) return a[l];
    if(l < k) return qsort(l + 1, right);
    else return qsort(left, l - 1);
}
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    printf("%d", qsort(1, n));
}

逆序对
１．归并

#include <iostream>
using namespace std;
const int maxn = 5e5 + 5 ;

int n, m;
int a[maxn], b[maxn];
int cnt;

void merges(int l, int r) {
    if(r - l < 1)
        return ;
    int mid=l + r >> 1;
    merges(l, mid);
    merges(mid + 1, r);
    int i = l, j = mid + 1;
    for(int k = l; k <= r; k++) {
        if(j > r || i <= mid && a[i] <= a[j])
            b[k] = a[i++];
        else
            b[k] = a[j++], cnt += mid - i + 1;
    }
    for(int k = l; k <= r; k++)
        a[k] = b[k];
}

signed main() {
    while(cin >> n, n) {
        cnt = 0;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        merges(1, n);
        cout << cnt << endl;
    }
    return 0;
}

2. 树状数组
   数据大时离散化．．．

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 5e5 + 5 ;

int n, m;
int c[maxn];
int lowbit(int x) {
    return (-x) & x;
}

void add(int x, int y){
    while(x <= n) {
        c[x] += y;
        x += lowbit(x);
    }
}

int get_sum(int x) {
    int res = 0;
    while(x){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

int main() {
    while(cin >> n, n) {
        int cnt = 0;
        memset(c, 0, sizeof(c));
        for(int i = 1, t; i <= n; i++){
            cin >> t;
            cnt += get_sum(n) - get_sum(t);
            add(t, 1);
        }
        cout << cnt << endl;
    }
    return 0;
}

奇数码问题　
ｐｓ：逆序对奇数和偶数　相同有解

倍增

天才ＡＣＭ　　倍增

归并完成对Ｂ的排序　ｃｈｋ从中找最大
如果　超过的话　还原Ｂ数组(A);
没有的话　保留排序　下一次就可以从ｎｒ开始排序　减低复杂度
倍增找到最长可行区间　使分段最少

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
int K, N, M, ans;
int A[maxn], B[maxn], C[maxn];
ll T;
 
bool chk(int cnt){
    ll res = 0;
    int p = 1,q = cnt, ms = M;
    while(p < q && ms --){
        ll s = C[q] - C[p];
        res += s * s;
        if(res > T) return false;
        p++, q--;
    }
    return true;
}
 
bool combine(int l,int r,int nr){
    sort(B + r + 1,B + nr + 1);
    int p = l,q = r + 1;
    int cnt = 0;
    while(p <= r && q <= nr){
        if(B[p] < B[q])  C[++ cnt] = B[p ++];
        else C[++ cnt] = B[q ++];
    }
    while(p <= r) C[++ cnt] = B[p ++];
    while(q <= nr) C[++ cnt] = B[q ++];
    if(chk(cnt)){
        int i = l;
        for(int i = l; i <= nr; i ++ ) A[i] = B[i] = C[i - l + 1];
        return true;
    }
    else{
        for(int i = r + 1;i <= nr;i++)  B[i] = A[i];
        return false;
    }   
}
 
void solve(){
    int l = 1,r = 1;
    ans = 0;
    while(l <= N){
        int nr,d = 1;
        while(d){
            nr =  r + d;
            if(nr <= N && combine(l,r,nr)) r = nr,d *= 2;
            else d /= 2;
        }
        ans++;
        r = l = r + 1;
    }
}
int main(){
    cin >> K;
    while(K --){
        cin >> N >> M >> T;
        for(int i = 1; i <= N; i ++) cin >> A[i], B[i] = A[i];
        solve();
        cout<<ans<<endl;
    }
    return 0;
}

ＳＴ表
https://www.luogu.org/problemnew/show/P3865

#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 1e5 + 5;

int lg[maxn];
int a[maxn], f[maxn][30];

int n, m;

void STbuild() {
    for(int i = 1; i <= n; i ++ ) f[i][0] = a[i];
    int t = (lg[n]-1)/(lg[2]-1) + 1;
    for(int j = 1; j < t; j ++ ) {
        for(int i = 1; i <= n - (1 << j) + 1; i ++ ) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int STquery(int l, int r){
    int k = (lg[r - l + 1] - 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    for(int i = 1; i < maxn; i ++){
        lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
    }
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
    }
    STbuild();
    for(int i = 1; i <= m; i ++) {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", STquery(x, y));
    }
    return 0;
}