imicola CR1037 div.3 题解
CR1037 div.3 题解

CR1037 div.3 题解

687 字 · 约 2 分钟

CR1037 题解

A

题意 :

输入一个数nn,找到最小的和它有共同数字的数 kk

思路:

显然kk就是这个数nn的所有位数的最小的那一位

void solve()
{
    int n;
    cin >> n;
    string s = to_string(n);
    sort(all(s));
    cout << s[0] << endl;
}
cpp

B

题意:

给定一个包含nn个元素的数组AA和一个数kk ,AA中的每个元素由 0,10,1 构成,需要我们寻找kk数量的连续00串且每个串之间需要有一个元素相隔

思路:

直接模拟即可

void solve()
{
    int n, k;
    cin >> n >> k;
    vint v(n);
    for (auto &&i : v) {
        cin >> i;
    }
    int cnt = 0;
    int now = 0;
    for (size_t i = 0; i < n; i++)
    {
        if(v[i] == 0)now++;
        if(v[i] == 1)now = 0;
        if(now == k){
            i++;
            cnt++;
            now = 0;
        }
    }
    cout << cnt << endl;
}
cpp

C

题意:

给定两个数 n,kn,k 和一个有 nn 个元素的数组 AA ,有一个从00开始的每秒加11的水位,数组AA中的元素aia_i表示第ii座塔的高度,你初始在aka_k 高度的塔上,你可以花费 ∣aj−ai∣|a_j - a_i| 的时间从第ii座塔移动到第jj座塔,当水位完全超过你所在塔的高度的时候便会失败

你需要判断能否到达最高的塔而不失败

思路:

我们考虑贪心,因为水位上涨速度与我们移动速度是一致的,故只要从我们目前所在高度的 aia_i 到最高位置 amaxa_{max} 之间从小到大两两的距离差都小于初始高度aia_i 我们就可以到达最高的塔

void solve()
{
    int n, k;
    cin >> n >> k;
    vint v(n);
    for (auto &&i : v) {
        cin >> i;
    }
    int under = v[k - 1];
    // 贪心:一开始所在位置就是我们能跨越的最大位置,而且我们只需要看比一开始大的
    ranges::sort(v);
    vint res;
    for (size_t i = 0; i < n; i++) {
        if (v[i] >= under) {
            res.emplace_back(v[i]);
        }
    }
    vint diff(n,0);
    for (size_t i = 0; i + 1 < res.size(); i++) {
        diff[i] = res[i + 1] - res[i];
    }
    cout << (ranges::max(diff) > under ? "NO" : "YES") << endl;
}
cpp

D

题意:

给定 nn 个赌场,其有三个参数 l,r,reall,r,real ,再给定初始金币 kk ,规定持有金币数量pp每个赌场只能允许p∈[l,r]p \in [l,r] 进入并且会将 pp 变为 realreal ,并且每个赌场只能进入一次

我们需要知道我们在参加任意次赌场后获得的最大金币数量为多少

思路:

由于我们需要最大的金币数量,所以我们每一次游玩后都想要金币尽可能上涨,这里我们考虑使用 大堆顶 即优先队列来筛选,其存放数据为{r,real}\{r,real\}

具体做法是

  • 先将所有赌场的进入门槛 ll 从小到大排序
  • 然后进行循环,首先令 now=know = k
    • 对当前金币nownow ,将l≤nowl \le now 的放入大堆顶,这样存放进入的数据中会按照realreal的大小排序
    • 对堆里的数据,先排除 r<nowr < now 的
    • 如果堆空了或者堆顶的real≤nowreal \le now 的话说明已经没有比 nownow 还大的元素了,那么我们就退出循环
    • 否则就将 nownow 赋值为堆顶的realreal 代表这一轮找到了最大的realireal_i 然后重复循环
struct st
{
    int l, r, re;
};

void solve()
{
    int n,k;
    cin >> n >> k;
    vector<st> v(n);
    for (size_t i = 0; i < n; i++)
    {
        auto &&[l, r, t] = v[i];
        cin >> l >> r >> t;
    }
    ranges::sort(v, [](st a, st b) { return a.l < b.l; });
    priority_queue<pii> pq;
    int now = k;
    int idx = 0;
    while (1)
    {
        while (idx < n && v[idx].l <= now)
        {
            pq.emplace(v[idx].re, v[idx].r);
            idx++;
        }
        // 排除 r < now的
        while (!pq.empty() && pq.top().second < now)
        {
            pq.pop();
        }
        // 如果空或者没有比x大的,那么就退出
        if (pq.empty() || pq.top().first <= now) {
            break;
        }
        // 提升now
        now = pq.top().first;
        pq.pop();
    }
    cout << now << endl;
}
cpp