Contestant(alt). Rank 6738. Rating -86 (+414 -500).

A. Yet Another Promotion

题意

定义两天内提供购物服务，每天的货物价格分别为 $a, b$，在第一天存在促销活动，购买 $m$ 个货物后会赠送一个。输出购买 $n$ 个货物的最少花费。

思路

对于 $m+1$ 个所需货物，$m a $ 和 $(m + 1) \times b$ 分别为第一天和第二天的价格，那么我们只需分类讨论即可：

前者小，那么我们将能参与促销的货物全都在第一天购买，也就是总共有 $\lfloor \frac{n}{m + 1} \rfloor \times m$ 个货物是参与了促销。此时，我们得到了 $\lfloor \frac{n}{m + 1} \rfloor \times (m + 1)$ 个货物，那么剩余的货物就作为正常购买，我们用 $\min(a,b)$ 购买即可；
后者小，直接全都在第二天买即可。

时间复杂度：$O(1)$

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int a, b, n, m;
        cin >> a >> b >> n >> m;
        cout << min(n * b, (n / (m + 1)) * m * a + (n - (n / (m + 1)) * (m + 1)) * min(a, b)) << '\n';
    }
    return 0;
}

一个大铸币没看懂题卡了半天

B. Fedya and Array

题意

给出如下定义：

若一个元素的相邻元素都比它大，那么定义其为 local minimum；若一个元素的相邻元素都比它小，那么定义其为 local maximum。

给定一个首尾相连的序列中 local maximum 的总和和 local minimum 的总和 $x, y$，构建该序列，满足相邻数相差 $1$，且长度最短。

思路

显然，$y, y-1, \ldots , x , x + 1 , \ldots, y - 1$ 一定是一个符合条件的序列，下面我们来证明一下可行性：

若 $a_i$ 和 $b_i$ 为相邻的 local maximum 和 local minimum ，那么对于 $a_i$，想要得到 $b_i$，就必须得有 $a_i - b_i$ 个数字，因而我们可以得到下面的式子：

$len = (a_1 - b_1) + (a_2 - b_1) + (a_2 - b_2) + \ldots + (a_k - b_k) + (a_1 - b_k)$

化简即可得到 $2(x - y)$，证毕。

时间复杂度：$O(n)$

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];

signed main() {
    ios::sync_with_stdio(0);
    int t, x, y;
    cin >> t;
    while(t --){
        cin >> x >> y;
        vector<int> ans;
        for(int i=x;i>y;i--) ans.emplace_back(i);
        for(int i=y;i<x;i++) ans.emplace_back(i);
        cout << ans.size() << '\n';
        for(auto &i : ans) cout << i << ' ';
        cout << '\n';
    }
    return 0;
}

好妙的做法

C. Dora and Search

题意

给定一个排列，输出一段连续区间的左右端点的下标，满足两个端点既不是区间内的最大值，也不是区间内的最小值。

思路

我们可以用类似双指针的方法，从两侧开始夹逼，只要去除区间外的点后，最大值和最小值都不在端点，那就直接输出。

时间复杂度：$O(n)$

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];

signed main() {
    ios::sync_with_stdio(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i=0;i<n;i++) cin >> a[i];
        int l = 0, r = n - 1, vl = 1, vr = n;
        while(l <= r){
            if(a[l] == vl) l ++, vl ++;
            else if(a[l] == vr) l ++, vr --;
            else if(a[r] == vl) r --, vl ++;
            else if(a[r] == vr) r --, vr --;
            else break;
        }
        if(l <= r) cout << l + 1 << ' ' << r + 1 << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}

不是排列的话就只有找拐点了