codeforces 1197A. DIY Wooden Ladder ,B. Pillars, C. Array Splitting

A. DIY Wooden Ladder
제목 링크: codeforces 1197A
제목:
n개의 널빤지를 제시하고 구성할 수 있는 사다리가 최대 몇 개냐고 묻는다.
문제 풀이:
가장 긴 널빤지 두 개를 양쪽으로 하고 나머지는 모두 페달로 하여 비교해 보면 된다

#include 
using namespace std;
int main(){
	int t;
	cin >> t;
	while(t--){
		int n, a[200005];
		cin >> n;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
		}
		sort(a+1, a+1+n);
		cout << min(a[n-1]-1, n-2) << endl;
	}
	return 0;
} 

B. Pillars
제목 링크: codeforces 1197B
제목:
n개의 접시 반경을 주고, 작은 접시만 큰 접시 위에 놓을 수 있으며, 최종적으로 모든 접시를 한 위에 놓을 수 있느냐고 묻는다.
문제 풀이:
시뮬레이션, 가장 큰 것을 찾은 후 두 개의 바늘로 좌우로 조작하다

#include
using namespace std;
#define ll long long
int main(){
   int n, m;
   while(cin >> n){
   	int a[500005], maxx = 0, k = 0, L = 0, R = 0, f = 1;
   	for(int i = 1; i <= n; i++){
   		cin >> a[i];
   		if(a[i] > maxx){
   			maxx = a[i];
   			k = i;
			}
		}
		L = k - 1; R = k + 1;
		a[0] = 0;
		a[n+1] = 0;
		while(1){
			if(L == 0 && R == n+1){    //        
				break;
			}
			if(a[L] >= a[k] || a[R] >= a[k]){  //             ，   
				f = 0;
				break;
			}
			else{
				if(a[L] > a[R] && L > 0){  //   
					k = L;
					L--;
				}
				else{     //   
					k = R;
					R++;
				}
				
			}
		}
		if(f == 1 && L == 0 && R == n+1){
			cout << "YES" << endl;
		}
		else{
			cout << "NO" << endl;
		}
	}
	return 0;
}

C. Array Splitting
제목 링크: codeforces 1197C
제목:
n개의 작은 그룹에서 큰 그룹으로 정렬된 그룹을 정하고 k개의 비공식적으로 인접한 하위 그룹으로 나눈다. 각 그룹의 값은 최대값에서 최소값을 빼고 최소 총계를 구한다.
문제 풀이:
만약 그룹을 나누지 않는다면, 그룹의 최대에서 그룹의 최소를 빼고, 즉 인접한 원소 간의 차이의 합이다
욕심 많은 사상, 인접한 원소의 차이를 정렬, 빼면 k개가 답이다

#include 
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
ll a[maxn], d[maxn];
int main(){
	int n, k;
	ll ans = 0;
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		d[i] = a[i] - a[i-1];
		ans += d[i];
	}
	ans = ans - d[1];
	d[1] = 0;
	sort(d+1, d+1+n);
	k--;
	while(k--){
		ans = ans - d[n];
		n--;
	}
	cout << ans << endl;
	return 0;
}