Educational Codeforces Round 69 (Rated for Div. 2)

Educational Codeforces Round 69 (Rated for Div. 2)

A - DIY Wooden Ladder

题意：给出不同长度的木棍，求最大能组成多少阶梯的梯子
题解：全部棍子升序排序，找出第二长的，然后其他可以在长度为n的木棍上放下n-1条棍子，或者是除去两根最长的其他都能放下，所以求两者最小值即可。

#include <cstdio>
#include <algorithm>
using namespace std ;
const int N = 1e5 + 5 ;
int a[N] ; 
int main(){
	int n , t ; 
	scanf ("%d",&t) ;
	while(t --){
		scanf("%d",&n) ; 
		for(int i = 1 ; i <= n ; ++ i)
			scanf ("%d",&a[i]) ;
		sort(a+1,a+1+n) ; 
		printf ("%d\n",min(a[n-1]-1,n-2)) ;
	}	
	return 0 ; 
}

B - Pillars

题意：有n个柱子，每个柱子上有半径为r的光碟，每次移动的光碟所在的柱子只能有一张光碟，且只能小的光碟移动到大的光碟上，并且只能在相邻的柱子上移动。
题解：光碟半径为n的左边递增，右边递减。

#include <cstdio>
#include <algorithm>
using namespace std ;
const int N = 2e5 + 5 ;
int a[N] ; 
int n ; 
bool check(){
	for (int i = 2 ; i <= n ; ++ i){
		if (a[i] > a[i-1])	continue ; 
		else{
			for (int j = i+1 ; j <= n ; ++ j){
				if (a[j] < a[j-1])	continue ; 
				else{
					return false ; 
				}	
			}
			return true ;
		}
	}
	return true ; 
}
int main(){
	scanf("%d",&n) ; 
	for(int i = 1 ; i <= n ; ++ i)
		scanf ("%d",&a[i]) ;
	if (check())	printf ("YES\n") ;
	else	printf ("NO\n") ;
	return 0 ; 
}

C - Array Splitting

题意：给出长度为n的数列和数字k，要求把n分为k份，每一份数列的值为其中的最大值减去最小值，求分割完之后的总价值最小为多少。
题解：求数列的前一个数和后一个数的差，将新的数列排序，删去最后k-1个即可（即求前n-k+1个的和）。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std ;
const int N = 3e5 + 5 ;
int a[N] , b[N] ; 
int n ;  
int main(){
	int n , k ; 
	scanf("%d%d",&n,&k) ; 
	scanf ("%d",&a[1]) ;
	for(int i = 2 ; i <= n ; ++ i){
		scanf ("%d",&a[i]) ;
		b[i] = a[i] - a[i-1] ; 
	}
	sort(b+2,b+n+1) ;
	long long ans = 0 ; 
	for (int i = 2 ; i <= n-k+1 ; ++ i){
		ans += b[i] ;
	}
	cout << ans << endl ;
	return 0 ; 
}

D. Yet Another Subarray Problem

题意：给出长度为n的数列和m、k，求下图公式的最大值

题解：
每个m个数就要减去一个k，枚举最右边的数然后比较（emmmmmm说实话我还是有点似懂非懂，再好好想想）。

#include <cstdio>
#include <algorithm>
using namespace std ; 
const int N = 3e5 + 5 ; 
typedef long long ll ; 
ll num[N] ;  
int main(){
	int n , m , k ; 
	scanf ("%d%d%d",&n,&m,&k) ;
	for (int i = 1 ; i <= n ; ++ i)
		scanf ("%lld",&num[i]) ;
	ll ans = 0 ; 
	for (int j = 0 ; j < m ; ++ j){
		ll now = 0 ; 
		for (int i = 1 ; i <= n ; ++ i){
			now += num[i] ; 
			if (i%m == j){	//选择的数字已满一组 
				now -= k ; 
				ans = max(ans,now) ;
			}
			if (now < 0)	now = 0 ;  
		}
	} 
	printf ("%lld\n",ans) ;
	return 0 ;
}