[数据结构与算法]Codeforces Round #610 (Div. 2)

呜呜这场好难

A - Temporarily unavailable

题意

给定一个数轴，一个人从a点走到b点，c点有一个基站，覆盖半径是r，问这个人在走的过程中有多长时间没有信号

这个人的速度为1单位/分钟

题解

我们确定在$[a,b]$区间内有多长的区间是有信号的，那么信号的起点就是$max(a,c?r)$，这里假设$a\le b$，

那么同理，信号的终点就是$min(b,c+r)$

那么没有覆盖到的区间就是$b?a?(min(b,c+r)?max(a,c?r))$

Code

int a, b, c, r;

void solve(){
    cin >> a >> b >> c >> r;
    if(a > b) swap(a, b);
    int st = max(a, c - r);
    int ed = min(b, c + r);

    cout << b - a - max(0, ed - st) << Endl;
}

B2 - K for the Price of One (Hard Version)

题意

有n个商品，p元钱

可以花$w_i$来买第$i$个商品，也可以一次买$k$个商品，而只需要花$max(a_{i_k})$

问最多能买多少个商品

题解1

这个题我们很容易的想到来用贪心来做，但是怎么贪确实学到了

我们首先明白第一个道理，单买一个高价值的不如单买一个低价值的

买k个的时候选比它小k-1个名次的肯定更好，这个很容易证明

那么我们知道，如果我们一次要买k个的话，一定是要买第k大的数开始买是最好的

其次如果买k个的话，肯定要是从小到大选择一个然后来以这个为起点选k个来买是最好的

那么如果我们单买的话也只会从前k-1个开始买了

题解2

看了看dp做法，但是对于菜鸡来说dp看题解简单，做起来难

首先上面的分析仍然适用

我们定义$dp[i]$为以$i$买以i号结尾的全部物品的最小价格

$dp[i]=min(dp[i?1]+w[i],dp[i?k]+w[i])$

Code

1

int n, p, k;
int a[N];
int s[N];

void solve(){
    cin >> n >> p >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = 0;
    }

    sort(a + 1, a + 1 + n);

    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

    int ans = 0;
    
    for(int i = 0; i < k; i++){
        
        int summ = s[i];
        if(summ > p){
            break;
        }

        int cnt = i;

        for(int j = i + k; j <= n; j += k){
            if(summ + a[j] <= p){
                summ += a[j];
                cnt += k;
            }
            else break; 
        }

        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

2

int n, p, k;
int a[N];
int f[N];

void solve(){
    cin >> n >> p >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; i++){
        f[i] = f[i - 1] + a[i];
        if(i >= k)
            f[i] = min(f[i], f[i - k] + a[i]);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++){
        if(p >= f[i])
            ans = i;
    }
    cout << ans << endl;
}

C - Petya and Exam

题意

Petya将会参加一场考试，这场考试从时间点0开始，到T结束。考试中有n道题，分为两种，简单（需要花a时间做完）的题和困难（需要花b时间做完）的题（a <= b），即在时间点x开始做这道题，将会在x+a或x+b时间点完成。现在每道题会在时间点 ti 变成必须完成，Petya可以在0 ~ T任意一个时间点离开，若离开时有必须要完成的题目没有完成，他将会得到0分，否则会得到他完成的题目的分数。求他最大能得到的分数。

（来源洛谷）

题解

这个题的解法真的很妙，也又学到了

参考官方题解+https://www.bilibili.com/video/BV1FJ411s7E5?p=3

首先我们贪心的想，解决一个简单问题肯定是比解决一个难的问题是要优的

那么我们假设在t时间内交卷，那么我们必须完成的问题要花费ax+by，其中x为在t时间内必须完成的简单题的数量，同理，y为在t时间内必须完成的简单题的数量

那么我们解决了必须解决掉的时间，那么剩下的根据第一条原则，那么我们显然优先选简单的来做会更好，然后 有剩余的再选难的做

那么我们就只需要枚举每种时间，

那可不行，T的范围是1e9，是不能直接枚举的。

我们想一下，在枚举的过程中，显然有部分时间是没有必要算的，只有当时间到达$t_i$的时候才是必须要做的，那么在$t_i?1$的时间是不需要一定做这个的

所以我们枚举$t_i$，这样只需要枚举n次即可

Code

#define int ll

int T;
int n, m, a, b;
int h[N];

void solve(){
    cin >> n >> m >> a >> b;

    int cnta = 0;
    int cntb = 0;
    vector<PII> q;

    for (int i = 0; i < n; i++){
        cin >> h[i];
    }
    for (int i = 0; i < n; i++){
        int t;
        cin >> t;
        q.pb({t, h[i]});
        if(h[i])
            cntb++;
        else
            cnta++;
    }

    sort(all(q));
    q.pb({m + 1, 0}); // m+1是因为我们最长时间是m时间，但是在公式里我们用的是t-1

    int ans = 0;
    int x = 0, y = 0;

    for (int i = 0; i <= n; i++){
        int need = x * a + y * b;
        int has = q[i].x - 1 - need;
        if(has >= 0){
            int A = min(cnta - x, has / a);
            has -= A * a;
            int B = min(cntb - y, has / b);
            ans = max(ans, x + y + A + B);
        }

        int j = i;
        while (j <= n && q[i].x == q[j].x){ // 看看有多少在下一时刻是必须要做的
            if(q[j].y)
                y++;
            else
                x++;
            j++;
        }
        i = j - 1;
    }

    cout << ans << endl;
}