http://codeforces.com/contest/851/problem/D
수열이 주어진다.
각각의 수열값에 대하여 연산을 시행할 수 있다.
연산은 다음과 같이 두가지가 있다.
1. 해당 숫자를 없앤다. (cost x소모)
2. 숫자를 1 올린다. (cost y소모)
수열의 gcd를 1이 아니도록 만들때 소모되는 최소 cost를 구하는 문제이다.
당연히 대회때는 풀지 못했고 솔루션과 AC코드들을 참고해서 이해하는데도 한참걸렸다.
우선 수열의 값이 최대 $10^6$들어오므로 gcd를 2부터 $10^6$까지 올려보면서
수열들의 gcd를 현재 값으로 맞출때의 최소 cost를 구하면 된다.
최소 cost를 구하는 방법은 다음과 같다.
구간 [index + 1, index + gcd - 1]에 있는 $f$를 기준으로 [index + 1, $f$ - 1]에 포함되는 숫자들은 없애고
[$f$, index + gcd - 1]에 포함되는 숫자들은 index + gcd로 만드는것이다.
이 $f$를 구하는 방법은 이분탐색으로 구해도 되지만 간단하게 gcd - x/y로 구할 수도 있다.
숫자들을 없애는 연산이나 1씩증가시키는 연산에 대해서는 구간합과 구간개수를 이용하면 된다.
#include <cstdio>
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define MAX 1005555
long long N, x, y;
long long sum[MAX + 1], cnt[MAX + 1];
long long gcnt(int r, int l) {
if (r < l || l >= MAX) return 0;
r = min(r, MAX - 1);
return cnt[r] - (l <= 0 ? 0 : cnt[l - 1]);
}
long long gsum(int r, int l) {
if (r < l || l >= MAX) return 0;
r = min(r, MAX - 1);
return sum[r] - (l <= 0 ? 0 : sum[l - 1]);
}
int main() {
scanf("%lld%lld%lld", &N, &x, &y);
for (int n = 0, in;n < N;n++) {
scanf("%d", &in);
sum[in] += in;
cnt[in]++;
}
for (int n = 1;n <= MAX;n++) {
sum[n] += sum[n - 1];
cnt[n] += cnt[n - 1];
}
long long ans = N*x;
for (int g = 2;g < MAX;g++) {
int f = max(1, g - x / y);
long long query = 0;
for (int plus = 0; plus < MAX;plus += g) {
// [plus + 1, plus + f - 1] delete
query += gcnt(plus + f - 1, plus + 1) * x;
// [plus + f, plus + g - 1] plus
query += (gcnt(plus + g - 1, plus + f)*((plus + g) * 1LL) - gsum(plus + g - 1, plus + f))*y;
}
ans = min(ans, query);
}
printf("%lld\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기