Codeforces Round 953 (Div. 2) A - C 题解

因为有事只做了A-C，都比较简单，全是很简单的思维，明天有空还会添加上D，如果有人需要可以明天常来看看！

进入正题：

A. Alice and Books

题意：给你n个数字，将这些数字分到两堆里，每个堆取一个编号最上面的数字，问能取到的最大和是多少？

题解：其实很容易看出来，最后一个数字是必须取的，那么直接用前n-1个数字的最大值加上最后一个值求和即可。

代码：

#include
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , m , k , a[maxn] ;
void solve(){
	n = read() ;
	for(int i = 1 ; i <= n ; i ++){
		a[i] = read() ;
	} 
	ll Max = -1 ;
	for(int i = 1 ; i <= n - 1 ; i ++){
		Max = max(Max , a[i]) ;
	}
	cout << Max + a[n] << endl ;
}
int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

B. New Bakery

题意：给你三个数字n,a,b，可以选择一个k，在1<=i<=k" role="presentation" style="position: relative;">1<=i<=k$1<=i<=k$内，每次可以增加(b−i+1)" role="presentation" style="position: relative;">(b−i+1)$(b-i+1)$个硬币，剩下的(n-k)个数字，每个加上a，问能取到的最大值是多少？

题解：很明显，当b−i+1<=a" role="presentation" style="position: relative;">b−i+1<=a$b-i+1<=a$，就用a即可，直接列式子，出答案即可。

代码：

#include
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , m , k , a[maxn] ;
void solve(){
	n = read() ;
	m = read() ;
	k = read() ;
	if(m >= k){
		cout << m * n << endl ;
		return ;
	}
	else{
		ll res = k - m + 1 ;
		if(res > n){
			res = n ;	
		}
//		cout << min(n , k - m + 1) << endl ;
		cout << (((k - res + 1ll + k) * res) / 2ll) + max(0ll , (n - res)) * m << endl ;
 	}
}
int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

C. Manhattan Permutations

题意：给你一个定义曼哈顿价值，表示为|a1−1|+|a2−2|+....+|an−n|" role="presentation" style="position: relative;">|a1−1|+|a2−2|+....+|an−n|$|a_1-1|+|a_2-2|+....+|a_n-n|$，问找到一个最大的排列，能满足曼哈顿价值等于k，如果没法满足，输出NO。

题解：首先，交换两个数字，很明显不会出现奇数的情况，再看，如果交换三个数字，例如135，其实和交换15的价值是一样的，那么很明显，每次交换两个数字即可。交换总会有数据范围，因为是排列，肯定是倒序和正序碰到一起的时候是最大值，这样NO的情况就排除完了。再来看可以的情况，我们手模数据，会发现，交换(1,2)和交换(1,3)价值差2，每次都差2，那么第一次交换的最大值就是(1,n)，第二次就是(2,n-1)....，所以我们就用贪心，看看减到什么时候会小于0，最后再交换(l,(m/2)+l)即可，完美撒花！复杂度O(n/2)" role="presentation" style="position: relative;">O(n/2)$O(n/2)$。

代码：

#include
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , m , k , a[maxn] ;
void solve(){
	n = read() ;
	m = read() ;
	ll ans = 0 ;
	if(n % 2 == 1){
		ans += ((2ll + 2 * (n / 2)) * (n / 2)) ;
	}
	else{
		ans += ((1ll + (2 * (n / 2) - 1))) * (n / 2) ; 
	}
	if(m > ans || m % 2 == 1){
		cout << "NO\n" ;
		return ;
 	}
	else{
		for(int i = 1 ; i <= n ; i ++){
			a[i] = i ;
		}
		ll rt = (n - 1) * 2 ;
		ll l = 1 , r = n ;
		while(m > 0){
			if(m - rt >= 0){
				swap(a[l] , a[r]) ;
				m -= rt ;
				l ++ ;
				r -- ;
				rt -= 4 ;
			}
			else{
				ll Rt = (m / 2) + l ;
				swap(a[l] , a[Rt]) ;
				m = 0 ;
			}
		}
	}
	cout << "YES\n" ;
	for(int i = 1 ; i <= n ; i ++){
		cout << a[i] << " " ;
	}
	cout << endl ;
}
int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

喜欢作者的记得点上你们宝贵的关注哦~