12846 무서운 아르바이트 https://www.acmicpc.net/problem/12846
$(\sum_{i}^{N} A_{i})*(min_{i\in{N}} A_{i})$ 최댓값을 구하는 문제다.
따지고보면 둘다 같은 문제이다.
여러가지 방법으로 풀 수 있는데 나는 plane sweeping 방법으로 접근했다.
(사실 위의 그림을 보면 알겠지만 유명한 히스토그램 문제이다.)
여기서 높이가 높은 순으로 최대한 양쪽으로 퍼질 수 있는만큼 퍼지는 방식으로 구했다.
6과 5는 양쪽으로 퍼질 수 없지만 4는 양쪽 하나씩 퍼질 수 있다.
만들었다.
stack을 이용해 $O(N)$만에 해결하는 방식도 이와 유사하지만 이 방법에서는 stack을 쓰지 않고
정렬한다는 차이가있다.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
struct Bucket { int l, r; };
int N;
int arr[100001];
long long sum[100001];
pair<int, int> save[1000001];
vector<pair<int,int>> v;
bool visit[100001];
Bucket bucket[100001];
long long ans = 0;
void update(Bucket &buck, int l, int r) {
buck.l = l;
buck.r = r;
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d", &arr[n]), v.push_back({ arr[n],n });
for (int n = 0;n < N;n++) {
sum[n] += (long long)arr[n] + (n == 0 ? 0 : sum[n - 1]);
}
sort(v.begin(), v.end(), greater<pair<int, int>>());
for (int n = 0;n < N;++n) {
int here = v[n].first;
int idx = v[n].second;
int l = idx, r = idx;
if (visit[idx]) continue;
visit[idx] = true;
while (l - 1 >= 0 && (arr[l - 1] >= here || visit[l - 1])) {
if (visit[l - 1]) l = bucket[l - 1].l;
else visit[--l] = true;
}
while (r + 1 < N && (arr[r + 1] >= here || visit[r + 1])) {
if (visit[r + 1]) r = bucket[r + 1].r;
else visit[++r] = true;
}
update(bucket[l], l, r);
update(bucket[r], l, r);
ans = max(ans, (sum[r] - (l == 0 ? 0 : sum[l - 1])) * (long long)here);
}
printf("%lld\n", ans);
return 0;
}
| cs |
위에서 언급했듯이 히스토그램문제처럼 divide & conquer로 풀 수 있다.
#include <cstdio>
typedef long long ll;
inline ll min(ll a, ll b) { return a > b ? b : a; }
inline ll max(ll a, ll b) { return a < b ? b : a; }
int N;
ll arr[100001];
ll sum[100001];
ll solve(int l, int r) {
if (l == r) return arr[l] * arr[l];
int mid = (l + r) >> 1;
ll ret = max(solve(l, mid), solve(mid + 1, r));
int left = mid, right = mid + 1;
ll Min = min(arr[left], arr[right]);
ret = max(ret, (arr[left] + arr[right]) * Min);
while (l < left || right < r) {
if (l == left || (right < r && arr[right + 1] > arr[left - 1])) right++, Min = min(Min, arr[right]);
else left--, Min = min(Min, arr[left]);
ret = max(ret, (sum[right] - (left == 0 ? 0 : sum[left - 1]))*Min);
}
return ret;
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%lld", &arr[n]);
for (int n = 0;n < N;n++) sum[n] += arr[n] + (n == 0 ? 0 : sum[n - 1]);
printf("%lld\n", solve(0, N - 1));
return 0;
}
| cs |
