首页 > 代码库 > Codeforces Round #243 (Div. 2) C. Sereja and Swaps(优先队列 暴力)
Codeforces Round #243 (Div. 2) C. Sereja and Swaps(优先队列 暴力)
题目
题意:求任意连续序列的最大值,这个连续序列可以和其他的 值交换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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。