USACO 2022 December Contest Bronze 문제풀이 정리
Cow College
-
$c_i$를 정렬한 후에 $c$ array에서 $c_i$보다 크거나 같은 값의 개수를 구한 후, 최대의 tution 합과 최소의 tution을 구하면 되는 문제
- bruteforce를 이용시 $O(N^2)$ 이므로 TLE가 나게 된다.
- 즉 $O(N \times ? )$를 하여 TLE를 막아야한다.
solution
- lower_bound를 이용하여 배열에서 $c_i$보다 크거나 같은 원소의 개수를 세어준 후 tution 책정 task를 진행하면된다.
- $O(N logN)$ 의 시간복잡도를 가지게 된다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
int N; cin >> N;
vector<long long> c(N);
for(auto &i : c) cin >> i;
sort(c.begin(), c.end());
long long mincost = 0, mx = 0;
for(int i = 0;i<N;i++){
int cnt = N-(lower_bound(c.begin(),c.end(),c[i])-c.begin());
if(mx < cnt*c[i]) {mincost = c[i]; mx = cnt*c[i];}
if(mx == cnt*c[i]) mincost = min(mincost, c[i]);
}
cout << mx << " " << mincost <<"\n";
}
Feeding the Cows
- 길이가 N인 G 또는 H가 나열되어있는 문자열이 있음
- G또는 H는 K만큼 이동하여 풀을 뜯을 수 있고, G는 G-grass, H는 H-grass만 먹을 수 있음
- 최소한으로 grass를 심을 때의 개수와 그때의 모양을 찾아야함
solution
- g,h 라는 변수에 마지막으로 저장된 각 타입의 grass의 위치 + K를 저장
- 위치+K를 저장하는 이유는 해당 위치의 풀은 +K만큼 커버를 할 수 있기 때문이다.
- 만약 다음 소가 g 보다 멀리 있다면 이는 소의 위치 - K를 해도 풀의 위치보다 멀기 때문에 새로 풀을 심어야한다.
- 풀을 심어야한다면 가장 오른쪽에 빈 공간에 심는 것이 가장 효율적이다.(greedy)
#include <bits/stdc++.h>
using namespace std;
int main(void) {
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while (T--) {
int N, K, cnt = 0, g = -1, h = -1;
string A;
cin >> N >> K >> A;
string ans;
for (int i = 0; i < N; i++)
ans.push_back('.');
for (int i = 0; i < N; i++) {
if (A[i] == 'G' && i <= g)
continue;
if (A[i] == 'H' && i <= h)
continue;
int idx = min(i + K, N - 1);
while (ans[idx] != '.') {
idx--;
}
ans[idx] = A[i];
if (A[i] == 'G')
g = idx + K;
if (A[i] == 'H')
h = idx + K;
cnt++;
}
cout << cnt << "\n" << ans << "\n";
}
}