Codeforces Round 980 (Div. 2) A ~ D

Codeforces Round 980 (Div. 2)

A

发现 $a\ge b$ 时输出 $a$ 即可 ；

否则 $a-x\le b-2x$ ，解得 $x_{min}=b-a$ ，$res=a-x=2a-b$ ，但是必须 $\ge 0$

int const N = 1e5 + 10;
int n, m, a, b, c;

void solve(){
    cin >> a >> b;
    if(a >= b){
        cout << a << '\n';
    }
    else{
        cout << (2 * a - b >= 0 ? 2 * a - b : 0) << '\n';
    }
}

B

发现自己的最优策略就是每个可能还有瓶子的卡槽按一遍，如此循环重复。

对于一个 $0$ 的卡槽，必须还要按一次才知道他是空的。

因为每次看最小卡槽有多好少即可，所以数组 $O(n)$ 模拟一下即可。

int const N = 2e5 + 10;

int n, k, a[N];

void solve(){    
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int res = 0, s = 0, idx = 1;
    while(k){
        int now = a[idx] - s;
        if(now == 0 && k){
            idx ++;
            res ++;
            continue ;
        }
        if(now * (n - idx + 1) >= k){
            res += k;
            break;
        }
        k -= now * (n - idx + 1);
        res += now * (n - idx + 1);
        s += now;
    }
    cout << res << '\n';
}

C

对于 $(x_1,y_1)$ ，$(x_2,y_2)$ ，考虑交换他们，发现内部的逆序对不会变，所以考虑两个元素之间的即可。假设 $m{x}_1\ne m{x}_2$ ，将最大值所在的元素放在左边，最多两个逆序对，而最大值所在的放在右边，最少两个逆序对。假设 $m{x}_1=m{x}_2$ ，让 $mn$ 小的放在左边。

int n;

int const N = 1e5 + 10;

struct node{
	int x, y;
}a[N];

bool cmp(const node & a, const node & b){
	if(max(a.x, a.y) != max(b.x, b.y)) return max(a.x, a.y) < max(b.x, b.y);
	return min(a.x, a.y) < min(b.x, b.y);
}

void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i].x >> a[i].y; 
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; i ++){
    	auto [x, y] = a[i];
    	cout << x << ' ' << y << ' ';
    }
    cout << '\n';
}

D

设 $d{p}_i$ 为从 $1$ 走到 $i$ , 让多少点无效的最小值。

注意到 $b_i\le i$ ，这种点忽略它没有意义，一定不如直接拿了分数往左考虑优。

因此只考虑 $b_i>i$ 的点。

维护每个点的忽略代价，以及跳跃到的位置，小根堆维护。

对于 $d{p}_i$ ，就等于所有 $pos\ge i$ 的最小代价。

void solve(){
	int n;
	cin >> n;

	vector<int> dp(n + 1, 1e18);
	vector<int> a(n + 1), b(n + 1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
    }	
    for(int i = 1; i <= n; i ++){
    	cin >> b[i];
    } 
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;
    dp[1] = 0;
    for(int i = 1; i <= n; i ++){
    	while(heap.size() && b[heap.top().second] < i) heap.pop();
    	if(heap.size()) dp[i] = heap.top().first;
    	heap.push({dp[i] + a[i], i});
    }
    int res = 0, pre = 0;
    for(int i = 1; i <= n; i ++){
    	pre += a[i];
    	res = max(res, pre - dp[i]);
    }
    cout << res << '\n';
}