C/C++教程

AtCoder Beginner Contest 212 Solution

本文主要是介绍AtCoder Beginner Contest 212 Solution,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题解

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

 

 

剩下题待更。

这篇关于AtCoder Beginner Contest 212 Solution的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!