题解

A.Alloy

水题

B.Weak Password

水题 + 1；

C.Min Difference

首先想到排序

接下来我们思考 如果说 ai > bj 那么ai之后的所有数都不可能列入答案，所以更新j

否则 更新i

遍历复杂度为O（n + m）排序复杂度为（n log n + m log m）

#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define INF 1010000000
#define rep(i, n) for(int i = 0; i < n; ++i)

int n, m;
    int a[N];
    int b[N];
    int ans = INF;
signed main() {

    cin >> n >> m;
    rep(i, n)cin >> a[i];
    rep(i, m)cin >> b[i];
    sort(a, a + n);
    sort(b, b + m);
    int x = 0;
    int y = 0;
    while ((x < n) && (y < m)) {
        ans = min(ans, abs(a[x] - b[y]));
        if (a[x] > b[y])y ++;
        else x ++;
    }
    cout << ans << endl;
    return 0;
}

 

D.Querying Multiset

一道堆的裸题。

不过使堆里每个元素加上一个值，在入堆时候的sum处理，确实很妙，学到了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL sum = 0;
signed main() {

    priority_queue<LL,vector<LL>,greater<LL>> heap;
    cin >> n;
    while(n --)
    {
        int p,x;
        scanf("%lld",&p);
        if(p == 1)
        {
            scanf("%lld",&x);
            heap.push(x - sum);
        }
        else if(p == 2)
        {
            scanf("%lld",&x);
            sum += x;
        }
        else 
        {
            LL t = heap.top();
            heap.pop();
            cout << t + sum<< endl;
        }
    }
    return 0;
}

 

 

剩下题待更。