A - Candy Button

有一个按钮按下后就能获得一颗糖果，但是有一定的冷却，冷却期间按下就没有糖果。给我一串按下按钮的序列，求最后能获取多少糖果。

思路： 逐个模拟即可，过程中记录上次拿糖果的时间。

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    for (int i = 0;i<n;i++){
        cin >> a[i];
    }
    int res = 1;
    int t = a[0];
    for (int i = 1;i<n;i++) {
        if (a[i] - t >= c) {
            res +=1;
            t=a[i];
        }
    }
    cout << res << endl;
}

B - Hands on Ring (Easy)

两者手握着一个长度为的环。每次移动一只手到指定位置，过程中不可越过另一只手，求总操作步数。

思路：每次判断两个方向哪个方向不能走，然后走另一条路。通过绝对值求距离。

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, l;
    cin >> l >> n;
    getchar();
    char hand; int target;
    int lh = 1, rh = 2;
    int res = 0;
    for (int i = 0;i<n;i++){
        int step;
        scanf("%c %d\n", &hand, &target);
        if (hand == 'L'){
            step = abs(target - lh);
            if (step * 2 < l) {
                if ((target < rh && rh < lh) || (target > rh && rh > lh)) step = l - step;
            } else {
                if (((target < rh && rh < lh) || (target > rh && rh > lh))) step = l - step;
            }
            lh = target;
        } else if(hand == 'R') {
            step = abs(target - rh);
            if (step * 2 < l) {
                if ((target < lh && lh < rh) || (target > lh && lh > rh)) step = l - step;
            } else {
                if (((target < lh && lh < rh) || (target > lh && lh > rh))) step = l - step;
            }
            rh=target;
        } else {
            *((int*)0) = 1;
        }
        res += step;
    }
    cout << res << endl;
}

C - Prepare Another Box

给你n个玩具和n-1个箱子，然后让你买一个箱子使得所有玩具都能放进不同一个箱子，要求新买的箱子尽可能小。没有答案输出-1，否则输出购买的箱子大小。

思路：最后购买的箱子的大小肯定是一个不能装进现有箱子的玩具的大小，将箱子和玩具降序，然后一一匹配，如果只有一个玩具装不下，输出该玩具的大小，否则输出-1。

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n; cin >> n;
    vector<int> a(n),b(n-1);
    for (int i = 0; i<n;i++){
        cin >> a[i];
    }
    for (int i = 0; i<n-1;i++){
        cin >> b[i];
    }
    sort(a.begin(), a.end(), greater()); sort(b.begin(), b.end(), greater());
    int flag = 0;
    for (int i = 0,j=0; i<n && j<n-1;i++,j++){
        if (a[i] > b[j]) {
            if (flag == 0){
                flag = a[i];
                j--;
            } else {
                flag = -1;
                break;
            }
        }
    }
    if (flag == 0) flag = a[n-1];
    cout << flag << endl;
}

D - Cycle

给你一个简单有向图，输出包含节点1的最短的环的长度，没有环输出-1.

思路： 很明显的bfs从1出发，遇到第一个环就可以停止了。

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n,m;
    cin >> n>>m;
    vector<vector<int>> ns(n);
    for (int i = 0;i<m;i++){
        int a, b;
        cin >> a >> b;
        ns[a-1].push_back(b-1);
    }
    queue<pair<int, int>> q;
    q.push({0,1});
    bool flag =false;
    int res = 0;
    while(!q.empty()){
        auto e = q.front(); q.pop();
        if(e.first == 0 && e.second != 1){
            res = e.second;
            break;
        }
        for (auto i : ns[e.first]){
            q.push({i, e.second+1});
        }
    }
    cout << res - 1 << endl;
}

E - Max × Sum

给出两个长为N有序数组A，B。在1~N中选择K个数字作为下标，使得每个下标i对应的Ai的最大值*每个下标i对应的Bi的和最小，输出这个最小值。

思路： 可以利用枚举和贪心，先从小到大枚举Ai的值，同时维护K个Bi的和。枚举过程通过给A列表排序，逐个枚举Ai，然后不断加入新的Ai，淘汰旧的Ai，将要淘汰的Ai用贪心决定即Bi最大值对应的Ai，所以要维护Bi的最大值，可以用优先队列。枚举过程中res不断取较小值。最后的res即为答案。

#include <bits/stdc++.h>

using namespace std;
void solve(){
    long long n,k;
    cin >> n >> k;
    long long a[n], b[n];
    for(long long i =0;i<n;i++) cin >> a[i];
    for(long long i =0;i<n;i++) cin >> b[i];
    vector<pair<long long, long long>> ns(n);
    for(long long i =0;i<n;i++) {ns[i] = {a[i], b[i]};};
    sort(ns.begin(), ns.end());
    long long res = INTMAX_MAX;
    priority_queue<pair<long long, long long>> heap;
    long long sum = 0;
    long long maxx = ns[k-1].first;
    for (long long i = 0; i<k;i++) {
        heap.push({ns[i].second, ns[i].first});
        sum+=ns[i].second;
    }
    for(long long i = k;i<n;i++){
        res = min(res, sum*maxx);
        auto e= heap.top();
        heap.pop();
        sum-=e.first;
        heap.push({ns[i].second, ns[i].first});
        sum+=ns[i].second;
        maxx=ns[i].first;
    }
    res = min(res, sum*maxx);
    cout << res << endl;
}
int main(){
    long long tcs; cin >> tcs;
    while(tcs--) solve();
}