Codeforces 1111C Creative Snap 분할+욕심

Creative Snap
C. Creative Snap
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Thanos wants to destroy the avengers base, but he needs to destroy the avengers along with their base.
Let we represent their base with an array, where each position can be occupied by many avengers, but one avenger can occupy only one position. Length of their base is a perfect power of 22. Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:

if the current length is at least 22, divide the base into 22 equal halves and destroy them separately, or

burn the current base. If it contains no avenger in it, it takes AA amount of power, otherwise it takes his B⋅na⋅lB⋅na⋅l amount of power, where nana is the number of avengers and ll is the length of the current base.

Output the minimum power needed by Thanos to destroy the avengers' base.
Input
The first line contains four integers nn, kk, AA and BB (1≤n≤301≤n≤30, 1≤k≤1051≤k≤105, 1≤A,B≤1041≤A,B≤104), where 2n2n is the length of the base, kkis the number of avengers and AA and BB are the constants explained in the question.
The second line contains kk integers a1,a2,a3,…,aka1,a2,a3,…,ak (1≤ai≤2n1≤ai≤2n), where aiai represents the position of avenger in the base.
Output
Output one integer — the minimum power needed to destroy the avengers base.
이 문제는 처음 봤을 때 물기가 느껴졌어요. 데이터 범위를 자세히 보면...
사실 어렵지 않다. 주로 데이터 범위가 너무 넓다.이산화와 유사한 방법을 써야 한다.
배열 a를 정렬합니다.구간 [l, r]의 영웅 수량은 a의 첫 번째 r보다 큰 수의 하표에서 1을 빼고 a의 첫 번째 수가 l보다 큰 하표에서 1을 더하면 할 수 있다(k는 매우 작다).
그러나 가지치기에 주의해야 한다. 만약에 구간 [l, r]의 영웅 수량이 0이면 바로 A로 돌아간다.
위 코드:

#include 
using namespace std;
long long n, k, a, b;
long long hero[1000001];
long long solve(long long l, long long r) {
    long long num = upper_bound(hero + 1, hero + 1 + k, r) - lower_bound(hero + 1, hero + 1 + k, l);
    if (num == 0) return a;
    long long ans = (r - l + 1) * b * num;
    if (l >= r) return ans;
    ans = min(ans, solve(l, (l + r) / 2) + solve((l + r) / 2 + 1, r));
    return ans;
}
int main() {
    cin >> n >> k >> a >> b;
    for (long long i = 1; i <= k; i++) cin >> hero[i];
    sort(hero + 1, hero + 1 + k);
    cout << solve(1, (1 << n));
}

전재 대상:https://www.cnblogs.com/zcr-blog/p/11427268.html