¶Codeforces Round #667 (Div. 3) B、C、D、E 题解

¶B. Minimum Product #枚举 #贪心

¶题目链接

¶题意

给定四个整数$a, b, x, y$，其中$a\geq x, b\geq y$，你可以执行不超过$n$次的操作：选择$a$或者$b$，减一。操作保证$a$不会低于$x$，$b$不会低于$y$。现要你求出$a$与$b$的最小乘积。

¶分析

容易知道结论，要使乘积变小，一定是要将尽可能多的减少量放到某一个数，而不是将减少量均摊给两个数。[*不完全证明见后]

由此，最终结果无非是两种情况，1) 要么先对$a$做减法，只有当新$a$不能再做减法时，再对$b$做减法。2) 要么先对$b$做减法，只有当新$b$不能再做减法时，再对$a$做减法。于是我们对这两种情况得到的乘积进行比较，就能得到最小乘积了。

[不完全证明]：翻译自@pritishn思路，假设两个数字$a,b$，你可以将他们进行总共两次减法操作。无疑有三种选择：(i)$a-1, b-1$ ，得到的乘积为$ab-a-b+1$；(ii)$a-2, b$，得到乘积为$ab-2b$；(iii)$a, b-2$，得到乘积为$ab-2a$。

不妨设$b>a$，显然$ab-a-b+1>ab-a-b>(因为b>a)ab-2b$，显然情况(i)的乘积比情况(ii)大，同理也可以证明情况(ii)乘积比情况(iii)大。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int MOD = 1e4 + 7;
int q;
int main(){
    scanf("%d", &q);
    while(q--){
        ll a, b, x, y, n;
        scanf("%lld%lld%lld%lld%lld", &a, &b, &x, &y, &n);
        ll cura = max(a - n, x); //得到a的下限
        ll len = n - (a - cura);
        ll curb = max(b - len, y); //b的下限
        ll ans1 = cura * curb;

        curb = max(b - n, y);
        len = n - (b - curb);
        cura = max(a - len, x);
        ll ans2 = cura * curb;
        printf("%lld\n", min(ans1, ans2));
    }
    return 0;
}

¶C. Yet Another Array Restoration #数学 #暴力 #构造

¶题目链接

¶题意

你需要构造一个数组，其中它有$n$个不同正整数，同时它必须包含$x, y$两个已知正整数（$x<y$），这个数组($a_1<a_2<...<a_n$)经过升序排序后所有相邻元素必须差值相等，即$a_2-a_1=a_3-a_2=...=a_n-a_{n-1}$。现要你找到这样的数组并输出，同时该数组中的最大元素越小越好。

¶分析

题目要求构造的数组，显然是等差数列。因此我们核心思想就是确定首项及公差后，判断$x,y$是否在该数列即可。

怎么确定公差？我们知道公差一定是$y-x$的约数，$d_{max}=y-x$，我们就从$d=1$到$d=d_{max}$开始确定首项$a_0$，为了保证数组最大值越小越好，一定是希望$y$越接近最大值越好（即y前面能够拓展足够多的元素）。于是我们从$y$开始递减，如果能够向前拓展到$n$个元素，说明当前的$d$是最优的。如果不行，我们就将$a_0$确定在尽可能小的正整数，然后以$a_0, a_0+d, a_0+2d, ... , a_0+d*(n-1)$拓展元素，于是题目中要求的数组就确定下来了。公差的从小到大递增，一旦发现合法，同时又因为其枚举次序符合最优性，便可直接输出。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int MOD = 1e4 + 7;
int q;
int main(){
    scanf("%d", &q);
    while(q--){
        int n, x, y;
        scanf("%d%d%d", &n, &x, &y);
        int diff = y - x;
        for(int d = 1; d <= diff; d++){
            if(diff % d != 0) continue; //说明公差的整数倍并不是两值差值，x利用该公差无法到达y
            if(diff / d + 1 > n) continue; //说明该公差下，x到达y所经过的元素太多了
            int k = min((y - 1) / d, n - 1); //注意，(y-1)/d保证a0落在最接近于1的位置
            int a0 = y - k * d;
            for (int i = 0; i < n; i++){
                printf("%d%c", a0 + i * d, (i == n - 1) ? '\n' : ' ');
            }
            break;
        }
    }
    return 0;
}

¶D. Decrease the Sum of Digits #模拟 #暴力

¶题目链接

¶题意

给定正整数$n$，每次操作可对$n$($\leq 10^{18}$)自增。你需要求出最少操作次数（同时也就是“增数”），使得将$n$增至某个数后所有数位数字之和，不大于$s$。

¶分析

观察到$n$的长度最多为18，我们可以自数字低位到最高位，尝试对每一位进行归零（实际上就是将该位的数字加到进十），并实时检查当前递增后的$n$的数字之和是否满足题意，时间复杂度为$O(log^2_{10}(n))$，对于该数据范围十分稳妥。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int MOD = 1e4 + 7;
int q;
int sum[20];
int Cal(ll x){ //计算x所有数位之和
    int res = 0;
    while(x){
        res += (x % 10);
        x /= 10;
    }
    return res;
}
int main(){
    scanf("%d", &q);
    while(q--){
        ll n, tmp; int s, tot = 0;
        scanf("%lld%d", &n, &s);
        if(Cal(n) <= s) {
            printf("0\n"); continue;
        }
        ll mul = 1, ans = 0;
        for (int i = 0; i < 19; i++){
            int cur = (n / mul) % 10; //获得第i+1位数字
            ll diff = (10 - cur) * mul; //进位所需的差值
            n += diff; //包含进位
            ans += diff;
            if(Cal(n) <= s) break;
            mul *= 10;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

¶E. Two Platforms #二分 #枚举

¶题目链接

¶题意

(飞机和飞机场太不形象了)

有n个球，第$i$个球坐标为($x_i, y_i$)，他们正要掉下来，现在你只有两个长度为$k$的水平盘子(如果盘子左端点为$x$，则右端点为$x+k$，两端点也能装下球)，需要你放置将这两个盘子放置到某个位置，将尽可能多的掉下来的球装下。求最多能装多少个球。

¶分析

感谢@issue敲腻害的思路。

题目中的$y_i$对答案没有影响，我们只考虑$x_i$，因而首先将所有球$x$坐标升序排序。接着，我们先考虑拿一个盘子去接球，从右到左枚举所有球的坐标，通过二分算法计算出该盘子当前从左端点起，能接到的球数量。为什么从右到左遍历？因为我们需要后缀和数组ri实时维护在区间[$x[i], x[n]$]中，任何位置放下盘子，能接到球的最大数量。

然后我们再拿另一盘子去接，此时从左到右枚举球的起点，并二分出能接到的数量。那么最后更新答案时，其实就是以$i$作为分界线， 第一个盘子装下左区间[$x[i], x[i]+k$] 的球数量，再加上第二个盘子在右区间（该右区间不一定连接于左区间）装下的球最大数量。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+5;
int q, n, k;
int x[MAXN], y[MAXN], le[MAXN], ri[MAXN];
int main(){
    scanf("%d", &q);
    while(q--){
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n + 1; i++) ri[i] = 0;
        for(int i = 1; i <= n; i++) scanf("%d", &x[i]);
        for(int i = 1; i <= n; i++) scanf("%d", &y[i]);
        sort(x + 1, x + n + 1);
        for(int i = n; i >= 1; i--){
            int xfar = x[i] + k; //从第i个球的位置开始装，盘子能够到达的右端点
            int pos = upper_bound(x + 1, x + 1 + n, xfar) - x; //得到右端点对应索引
            ri[i] = max(pos - i, ri[i + 1]); //实时更新盘子放在[i, n]区间中任意位置中，接下球的最大数量
        }
        int ans = -1;
        for(int i = 1; i <= n; i++){ //从1开始枚举另一盘子的左端点
            int xfar = x[i] + k; //该盘子的右端点
            int pos = upper_bound(x + 1, x + 1 + n, xfar) - x; 
            ans = max(ans, pos - i + ri[pos]);
        }
        printf("%d\n", ans);
    }
    return 0;
}