首页 > 代码库 > Codeforces Round #243 (Div. 2) C. Sereja and Swaps(优先队列 暴力)

Codeforces Round #243 (Div. 2) C. Sereja and Swaps(优先队列 暴力)

2024-07-02 02:06:39   229人阅读

题目

题意：求任意连续序列的最大值，这个连续序列可以和其他的 值交换k次，求最大值

思路：暴力枚举所有的连续序列。没做对是因为 首先没有认真读题，没看清交换，然后，以为是dp或者贪心

用了一下贪心，各种bug不对。

 

这次用了一下优先队列，以前用的不多，看这个博客又学了一下

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <queue>
 6 using namespace std;
 7 const int maxn = 200+10;
 8 
 9 struct node
10 {
11     int x;
12     bool operator < (const node &tmp)const
13     {
14         return x > tmp.x;
15     }
16 };
17 int main()
18 {
19     int a[maxn], i, j, l;
20     int n, k, ans, t2, sum, t;
21     while(cin>>n>>k)
22     {
23         for(i = 0; i < n; i++)
24             cin>>a[i];
25         ans = a[0];
26 
27         for(i = 0; i < n; i++)
28             for(j = i; j < n; j++)
29         {
30             priority_queue<int>Max;
31             priority_queue<node>Min;
32             sum = 0;
33             for(l = 0; l < i; l++)
34                 Max.push(a[l]);
35             for(l = j+1; l < n; l++)
36                 Max.push(a[l]);
37             for(l = i; l <= j; l++)
38                 {
39                     Min.push((node){a[l]});
40                     sum += a[l];
41                 }
42 
43                 t2 = k;
44             while(t2 && !Max.empty() && Max.top() > Min.top().x)  //这要先判空，编译的时候错了一下
45             {
46                 t2--;
47                 sum -= Min.top().x;
48                 sum += Max.top();
49                 t = Max.top();
50                 Max.pop();
51                 Max.push(Min.top().x);
52                 Min.pop();
53                 Min.push((node){t});
54             }
55             if(sum > ans)
56                 ans = sum;
57         }
58         cout<<ans<<endl;
59     }
60     return 0;
61 }

 


联系
我们