Codeforces Round #727 (Div. 2) A~D

A.Contest Start

• 题意：有n名选手进行比赛，第i位选手的开始时间位(i - 1) * x，每位选手比赛的持续时间均为t，例如第1位选手开始比赛时间为：0，结束时间为：t, 第2位选手开始时间为x, 结束时间为x + t。每一位选手的不满意度为该选手到比赛结束时间， 比赛仍未结束（或者比赛刚开始）选手的数量，求所有选手不满意度之和。
• 思路：分类讨论 + 思维
• 解析：感觉自己的分类讨论写的有点麻烦（比赛的时候瞎搞），这里记录一下看到其他大佬的解法。（首先令cnt = t / x）
  1. 若 cnt >= (n-1)说明当每个人比赛结束时，它身后的所有人都开始比赛（并且仍未结束），此时总的不满意度为sum(n-1, n-2, n-3 ···, 1)，为一个等差数列求和;
  2. 否则，令num = n - cnt, num表示不满意度为cnt的人数，相当于第一个到第num个人的不满意度均为cnt，他们的不满意度总和为num * cnt，而到第num + 1个人时, 它身后已经没有cnt个人，所以第num + 1 -> 第n个人的不满意度之和为（cnt-1, cnt-2, ··· 1）的求和, 两者再进行相加即可。
• 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int k;
ll n, x, t;
int main()
{
    cin >> k;
    while(k --)
    {
        ll res = 0;
        cin >> n >> x >> t;
        ll cnt = t / x;
        if(cnt >= n - 1)
            res = n * (n-1) / 2;
        else
        {
            ll num = n - cnt;
            res = num * cnt + cnt * (cnt-1) / 2;
        }
        cout << res << endl;
    }
    return 0;
}

B.Love Song

• 题意：给出一个由a-z组成的字符串str, 若有a则a重复一次, 有b则b重复两次, 有c则重复三次，例如：abbcb，完成变换后：abbbbcccbb，给定一个[l, r]区间, 求该str在该区间根据上诉规则变换后字符串str‘的长度
• 思路：前缀和
• 解析：将原区间做一个前缀和预处理，记录完成变换操作后整个字符串的长度和，最后通过sum(r) - sum(l-1)即为结果。
• 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, q;
char str[N];
ll sum[N];
int main()
{
    cin >> n  >> q;
    cin >> str + 1;
    for(int i = 1; i <= n; i++)
        sum[i] += sum[i-1] + (ll)(str[i] - ‘a‘) + (ll)1;
    while(q --)
    {
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l-1] << endl;
    }
    return 0;
}

C.Stable Groups

• 题意：给出n个学生的成绩，若相邻的两个学生成绩之差不超过x，则该两个学生可以在一个稳定小组中，并且可以在这n个学生中加入任意成绩的k个学生，换言之，也就是将会有n名学生成绩已知，可有k名学生成绩任意，问这n + k名学生最少能组成几个稳定小组（k名学生可用可不用，相当于是一个辅助条件，可以帮助组成更少的稳定小组）
• 思路：贪心 + 思维
• 解析：首先将n名学生按成绩从小到大进行排序。
  1. 只有一名学生时特判一下;
  2. 否则当两个学生成绩差大于x时，按它们之间距离从小到大添加辅助学生（辅助学生就是那k名学生）（贪心思想）
     这里解释一下代码中的num数组，实际上是这两名学生中至少需要插入num名辅助学生的数量才能使得这两名学生在一个稳定小组，最后是根据num从小到大进行排序的，原理实际是一样的，那重点是这个num的求法，实际上是ceil(dis/x)-1【此处可以自行找规律】, 但这里会爆double，所以向上取整利用一个巧妙的规律：ceil(dis/x) = (dis + x - 1) / x即可，最后再根据一些条件消耗辅助学生减少稳定小组的数量即可。
• 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll num[N] ,a[N];
ll n, k, x;
int cnt = 0;
int main()
{
    cin >> n >> k >> x;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    if(n == 1) cout << 1 << endl;
    else
    {
        for(int i = 2; i <= n; i++)
        {
            ll dis = a[i] - a[i-1];
            if(dis > x)
                num[++cnt] = (dis + x - 1) / x - 1;
        }
        sort(num + 1, num + cnt + 1);
        int tcnt = cnt;
        for(int i = 1; i <= tcnt && k >= num[i]; i++)
        {
            k -= num[i];
            cnt --;
        }
        cout << cnt + 1<< endl;
    }
    return 0;
}

D.PriceFixed

• 题意：需要购买n种商品，每种商品所需购买的数量为ai, 当购买商品的总数量达到bi，则第i件商品价格为原来的价格的一半，求购买n件商品的最小花费。
• 思路：贪心 + 双指针
• 题解：根据题意，若想要最小花费购买完n种物品，那必然是希望更多的种类物品（准确来说是更多件物品）在购买时能打折，因为购买的单价都一样，说明每种物品的价值都一样，那么我们可以按照bi将物品种类进行排序，也就是先购买容易打折的物品，我们可以设置一个双指针进行遍历，将会出现两种情况：
  1. 当购买第i种商品可以打折时，直接购买ai件第i种商品即可（此时能打折，不买白不买）；
  2. 当购买第i种商品不能打折时，那就从尾指针r往前遍历，先购买b较大的商品进行凑数，总商品数量凑够bi后再购买第i种商品，这样就尽可能的多购买到打折的商品。
• 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n;
struct P
{
    ll a, b;
}p[N];
bool cmp(P x, P y)
{
    return x.b < y.b;
}
int main()
{
    ll sum = 0, cnt = 0; //总花费、当前已购买商品的数量
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> p[i].a >> p[i].b;
        sum += p[i].a * (ll)2;
    }
    sort(p + 1, p + 1 + n, cmp);
    int l = 1, r = n;
    while(l <= r)
    {
        if(cnt >= p[l].b) //当前商品所需数量达到打折的数量
        {
            cnt += p[l].a;
            sum -= p[l].a; //打折的商品数量
            l ++;
        }
        else
        {
            if(p[r].a + cnt >= p[l].b)
            {
                p[r].a -= p[l].b - cnt;
                cnt = p[l].b;
            }
            else //加上第r种商品仍不满足第l种商品能打折
            {
                cnt += p[r].a;
                r --;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Codeforces Round #727 (Div. 2) A~D

原文：https://www.cnblogs.com/K2MnO4/p/14946373.html