Atcoder beginner contest 376 • santisify Site

A.Candy Button#

题目描述#

一个按钮，按了会发糖。

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

解题思路#

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

参考代码#

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

cpp

B.Hands on Ring (Easy)#

Hands on Ring (Easy) ↗

题目描述#

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

解题思路#

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

参考代码#

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

cpp

C.Prepare Another Box#

Prepare Another Box ↗

题目描述#

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

解题思路#

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

参考代码#

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

cpp

D.Cycle#

Cycle ↗

题目描述#

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

解题思路#

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

参考代码#

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

cpp

E.Max × Sum#

Max × Sum ↗

题目描述#

给定 $n$ , $k$ 和两数组 $A$ , $B$ ， $S$ 是大小为 $k$ 的 ${1,2,…,N}$ 的子集,求 $\max_{i \in S} A_{i} * \sum_{i \in S}B_{i}$ 的最小值。

解题思路#

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

参考代码#

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

cpp