제출 #685241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
685241		omikron123	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	375 ms	13688 KiB

bridge

// https://oj.uz/problem/view/APIO15_bridge

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

// K=1,2, N=1e5, 需要O(nlogn)
// 1. 家和办公室在同一边的是不参与计算的，和桥没有关系。
// 2. 最小值都在event点上面取得，而且是一个U型的阶梯函数，所以应该可以固定一个桥的位置，然后binary search另外一个。
// 3. 进一步可以发现K=1的时候，答案就是S[i], T[i]的median. 
// 4. K=2的时候，简单做法是可以暴力搜索O(n^3)，这样可以得到31分。
// 5. 正解：把|s-x|+|t-x|画出来，就可以看到，是U型左右对称，所以有两个桥的时候，应该走的是离
//    (s+t)/2近的桥。所以可以按(s+t)/2排序，分成两段后分别求median。这里可以用sliding median
//    的方法（两个multiset求siding median），O(nlogn).

// 收获：解题需要画图和抽象成公式，需要在纸上抠细节，就能找到正确解法。

int n, K;
ll ans;
vector<pair<int,int>> x;

// sliding median with 2 multisets
struct median {
    multiset<int> l, r;     // l is smaller part. size(l) >= size(r)
    ll lsum, rsum;
    median() {
        lsum = 0; rsum = 0;
    }
    void balance() {
        while (l.size() > r.size() + 1) {
            int x = *prev(l.end());
            r.insert(x);
            l.erase(l.find(x));
            rsum += x, lsum -= x;
        }
        while (r.size() > l.size()) {
            int x = *r.begin();
            l.insert(x);
            r.erase(r.find(x));
            lsum += x, rsum -= x;
        }
    }
    void add(int x) {
        if (l.empty()) {
            l.insert(x);
            lsum = x;
            return;
        }
        if (x > get()) {
            r.insert(x);
            rsum += x;
        } else {
            l.insert(x);
            lsum += x;
        }
        balance();
    }
    int get() {
        return l.empty() ? -1 : *prev(l.end());
    }
    void del(int x) {
        if (x > get())
            r.erase(r.find(x)), rsum -= x;
        else
            l.erase(l.find(x)), lsum -= x;
        balance();
    }
};

int main() {
    scanf("%d %d", &K, &n);
    for (int i = 0; i < n; i++) {
        char c1[10], c2[10];
        int x1, x2;
        scanf("%s %d %s %d", c1, &x1, c2, &x2);
        if (c1[0] == c2[0]) ans += abs(x1-x2);
        else x.push_back({min(x1,x2), max(x1,x2)});
    }

    vector<int> X;
    for (auto p: x) {
        X.push_back(p.first);
        X.push_back(p.second);
    }
    sort(X.begin(), X.end());
    if (K == 1 && x.size()) {
        // just return the median of all numbers
        int m = X[X.size() / 2];
        for (auto p: x)
            ans += abs(p.first-m) + abs(p.second-m) + 1;
    } else if (K==2 && x.size()) {
        // 正解
        median l, r;    // l is smaller
        // sort x by (s+t)/2
        sort(x.begin(), x.end(), [](pi a, pi b) {
            return (a.first+a.second) < (b.first+b.second);
        });
        // initially everything in 'r'
        ll sum = 0;
        for (int p: X)
            r.add(p);
        int mr = r.get();
        ll ans2 = r.rsum - r.lsum + x.size();

        // move pairs one by one from r to l
        for (pi p: x) {
            l.add(p.first), l.add(p.second);
            r.del(p.first), r.del(p.second);
            ll sum = l.rsum - l.lsum + r.rsum - r.lsum + x.size();
            ans2 = min(ans2, sum);
        }
        ans += ans2;
    }

    printf("%lld", ans);

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:106:12: warning: unused variable 'sum' [-Wunused-variable]
  106 |         ll sum = 0;
      |            ^~~
bridge.cpp:109:13: warning: unused variable 'mr' [-Wunused-variable]
  109 |         int mr = r.get();
      |             ^~
bridge.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d", &K, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%s %d %s %d", c1, &x1, c2, &x2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37