526互联

Educational Codeforces Round 148 (Rated for Div. 2) D1. Red-Blue Operations

发布时间 2023-05-23 22:53:29作者: qdhys

Easy Version传送门
Hard Version传送门

题目大意：

解题思路：

   1.  不难发现，若k小于等于n，我们将a排序，a数组下标[1, k]区间上的每个数字依次加上 k, k - 1, ..., 1，取最小值就是答案。（下述操作都是基于排序a）

   2.  若k大于n，观察发现如果我们想让一个位置上的数字变得更大，那么操作次数必定为奇数次，只要n不为1，我们一定有方法能让操作的位置被操作奇数次。

   3.  若k大于n，观察发现若k和n的奇偶性一样

   4.  若k大于n，若k和n奇偶性相同，在不考虑最后n个操作以前的所有操作，也就是[1, k - n - 1]这些操作的情况下，那么n步最优的方案是把[k, k - n]这些数字依次加到a数组下标[1, n]。若n和k奇偶性不同，那么最后n - 1步最优的方案是把[k, k - n - 1]这些数字当成a数组下标[1, n]的最后一次奇数操作。若n和k奇偶性不同

#include <bits/stdc++.h>

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f * 2;
using ll = long long;

typedef std::pair<int, int> PII;
int n, m;

int a[N];
inline void solve() {
	std::cin >> n >> m;
	for (int i = 1; i <= n; i ++) std::cin >> a[i];
	std::vector<int> b(n + 1);
	std::sort(a + 1, a + n + 1);
	
	while (m --) {
		int x;
		std::cin >> x;
		int xx = x;
		if (n == 1) {
			if (x & 1) std::cout << a[1] + x - x / 2 << ' ';
			else std::cout << a[1] - x / 2 << ' ';
			continue;
		}
		

		if (x <= n) {
			int mn = INF;
			for (int i = 1, j = x; i <= n; i ++, j --) {
				if (j > 0)	mn = std::min(mn, a[i] + j);
				else mn = std::min(mn, a[i]);
			} 
				
			std::cout << mn << ' ';
			continue;
		}
		
		auto check = [&](int target, int t) -> int {
			for (int i = 1; i <= n; i ++) {
				if (b[i] <= target) continue;
				int c = b[i] - target;
				if (c > 0) {
					t -= c;
					if (t < 0) return -1;
				}
			}
			
			return t;
		};
		
		if ((n & 1) == (x & 1)) {//有n个可以加上去的
	 		for (int i = 1, j = x; i <= n; i ++, j --) 
	 			b[i] = a[i] + j;
	 		x -= n;
	 		x /= 2;
	 		
	 		int mn = INF;
	 		for (int i = 1; i <= n; i ++) mn = std::min(mn, b[i]);
	 		
	 		ll sum = 0;
	 		for (int i = 1; i <= n; i ++) 
	 			sum += b[i] - mn;
	 		
	 		if (sum >= x) std::cout << mn << ' ';
	 		else {
	 			x -= sum;
	 			std::cout << mn - (x + n - 1) / n << ' ';
	 		}
		} else {
	 		for (int i = 1, j = x; i < n; i ++, j --) 
	 			b[i] = a[i] + j;
	 		b[n] = a[n];
	 		x -= n - 1;
	 		x /= 2;
	 		
	 		int mn = INF;
	 		for (int i = 1; i <= n; i ++) mn = std::min(mn, b[i]);
			 		
	 		ll sum = 0;
	 		for (int i = 1; i <= n; i ++) 
	 			sum += b[i] - mn;
	 		
	 		if (sum >= x) std::cout << mn << ' ';
	 		else {
	 			x -= sum;
	 			std::cout << mn - (x + n - 1) / n << ' ';
	 		}
		}
	}
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int _ = 1;
    //std::cin >> _;
    while (_ --) solve();
    
    return 0;
}