Atcoder beginner contest 376

atcoder, 题解

A.Candy Button

Candy Button

题目描述

一个按钮，按了会发糖。

给定多次按的时间。如果这次按的时间距离上次发糖时间超过了，则发个糖。问发的糖数量。

解题思路

发糖的前提是距离上次发糖时间大于等于

参考代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
    int n, k, ct = 0;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for(int i = 0 ; i <n ; i ++) {
        std::cin >> a[i];
    }
    ct = 1;
    int pos = 0;
    for(int i = 1; i < n; i ++) {
        if(a[i] - a[pos] >= k) {
            ct ++;
            pos = i;
        }
    }

    std::cout << ct << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    // std::cin >> Lazy_boy_;
    while (Lazy_boy_--) solve();
    return 0;
}

B.Hands on Ring (Easy)

Hands on Ring (Easy)

题目描述

的环形格子。两个棋子，初始位于, 。
给定个指令，每个指令指定一个棋子移动到某个格子上，期间不能移动另外一个棋子。
依次执行这些指令，问移动的次数。

解题思路

简单模拟一下即可，可能我的代码有点“屎山”.

参考代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
    int n, q;
    std::cin >> n >> q;
    int res = 0;
    int l = 1, r = 2;
    while(q --) {
        char c;
        int x;
        std::cin >> c >> x;
        if(c == 'L' && x != l) {
            if(l < r) {
                if(x <= r) {
                    res += abs(x - l);
                }else {
                    res += (l + n - x);
                }
            }else {
                if(x >= r) {
                    res += abs(x - l);
                }else {
                    res += (x + n - l);
                }
            }
            l = x;
        }else if(c == 'R' && x != r){
            if(l < r) {
                if(x >= l) {
                    res += abs(r - x);
                }else {
                    res += (n - r + x);
                }
            }else {
                if(x <= l) {
                    res += abs(r - x);
                }else {
                    res += (r + n - x);
                }
            }
            r = x;
        }
    }

    std::cout << res << endl;
}


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    // std::cin >> Lazy_boy_;
    while (Lazy_boy_--) solve();
    return 0;
}

C.Prepare Another Box

Prepare Another Box

题目描述

给定个球的大小和个箱子的大小。现买一箱子，要求尺寸最小，使得个球恰好可以放进个箱子里,一个箱子有且只能放一个球。

解题思路

要求找出箱子大小的最小值，那么我们可以先排个序，若最后一个箱子越大，可以放入的方法就越多，反之越少。那么我们怎么求找到这个值呢？我们只需要一个箱子我们可以去尝试每一个大小箱子，但是这不现实，于是就可以想到二分，可以大大减小时间复杂度，二分条件便是查看是否有球无法放入箱子。二分完成后，要检查二分后的答案是否满足题意。

参考代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n - 1);
    for(int i = 0; i < n; i ++) {
        std::cin >> a[i];
    }

    for(int i = 0; i < n - 1; i ++) {
        std::cin >> b[i];
    }

    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    std::function<bool(int)> check = ([&](int x) -> bool {
        auto t = b;
        t.push_back(x);
        std::sort(t.begin(), t.end());
        for(int i = 0 ; i < n ; i ++) {
            if(a[i] > t[i]) return false;
        }
        return true;
    });

    int l = 1, r = inf;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            r = mid;
        }else {
            l = mid + 1;
        }
    }
    if(l == inf) {
        std::cout << -1 << endl;
    }else{
        std::cout << l << endl;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    // std::cin >> Lazy_boy_;
    while (Lazy_boy_--) solve();
    return 0;
}

D.Cycle

Cycle

题目描述

给定一张有向图，问包含点的环的最小环点数。

解题思路

要确保点数最小,且有回路，那么只有 ,从点，每次到达点时更新答案。

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
	int n, m;
	std::cin >> n >> m;
	std::vector a(n + 1, std::vector<int>());

	for(int i = 0; i < m; i++) {
		int u, v;
		std::cin >> u >> v;
		a[u].push_back(v);
	}

	std::vector<int> dis(n + 1, -1ll);
	std::queue<int> q;
	dis[1] = 0;
	q.push(1);
    int res = inf;
	while (q.size()) {
		auto t = q.front();
		q.pop();
		for(auto i : a[t]) {
			if(i == 1) {
				res = std::min(res, dis[t] + 1);
			}
			if(dis[i] == -1) {
				dis[i] = dis[t] + 1;
				q.push(i);
			}
		}
	}
	if(res > n) {
		std::cout << -1 << endl;
	}else {
		std::cout << res << endl;
	}
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int Lazy_boy_ = 1;
	// std::cin >> Lazy_boy_;
	while (Lazy_boy_--) solve();
	return 0;
}

E.Max × Sum

Max × Sum

题目描述

给定, 和两数组 ,，是大小为的的子集,求的最小值。

解题思路

枚举，剩下的问题就是找满足的前小的的和。首先对数组进行排序，并且数组与数组一同变化（可以用pair）。然后依次枚举，此即为。然后找中最小的个。考虑如何维护前小的和，因为会有不断的加入，会不断淘汰较大的，因此可以用优先队列维护这些在优先队列不断 push,pop时维护其里面的值的和即可。其时间复杂度为注意枚举时，是一定要选的，因此要从优先队列里求出前小的和（但第小的不能丢弃，它可能比小，只是因为此时必选，因而暂时不能选它）。

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
	int n, k;
	std::cin >> n >> k;

	std::vector<std::pair<int, int> > a(n);
	for(int i = 0; i < n; i++) {
		std::cin >> a[i].first;
	}

	for(int i = 0; i < n; i++) {
		std::cin >> a[i].second;
	}


	std::sort(a.begin(), a.end(), [&](pii aa, pii bb) {
		return aa.first < bb.first;
	});

	int s = 0;
	std::priority_queue<int, std::vector<int>, std::less<> > pq;
	for(int i = 0; i < k; i++) {
		pq.push(a[i].second);
		s += a[i].second;
    }

    int res = s * a[k - 1].first;
	for(int i = k; i < n; i++) {
		auto [x, y] = a[i];

		if (y < pq.top()) {
			s -= pq.top();
			pq.pop();
			pq.push(y);
			s += y;
		}

		res = std::min(res, s * x);
	}

	std::cout << res << endl;
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int Lazy_boy_ = 1;
	std::cin >> Lazy_boy_;
	while (Lazy_boy_--) solve();
	return 0;
}