Algoogle

Algorithm for Programming Contest

Codeforces 425A Sereja and Swaps

Category: Codeforces Tag: brute-force

Sereja and Swaps

問題概要


長さnの数列aのうち連続する要素の和の最大値を考える.
k回要素の位置をswapできるとき, 最大はいくらになるか.

解法


足し合わせる区間を決めたとき, swapするのはその区間の小さいものとその区間の外の大きいもの.
よって区間を全てみて, それぞれ外と中でpriority_queueをもってやるとよい.
入れ替えるのは内側の最小値が外側の最大値より小さいときに起こることに注意する.

コード


(425A.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

int n, k, a[256];

int solve()
{
        int ans = a[0];
        for (int l = 0; l < n; l++)
                for (int r = l; r < n; r++) {
                        priority_queue<int> in, out;
                        for (int i = 0; i < n; i++) {
                                if(i < l or r < i) out.push(a[i]);
                                else in.push(-a[i]);
                        }
                        int j = 0, sum = 0;
                        while(!in.empty() and !out.empty() and j < k) {
                                int x = -in.top(), y = out.top();
                                out.pop();
                                if(x < y) {
                                        j++;
                                        sum += y;
                                        in.pop();
                                }
                                else break;
                        }
                        while(!in.empty()) {
                                sum -= in.top();
                                in.pop();
                        }
                        ans = max(ans, sum);
                }

        return ans;
}

void input()
{
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];

}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments