[ACM_暴力] 最多交换k个数的顺序,求a[i]的最大连续和

简介:


 

复制代码
 1 /*
 2 http://codeforces.com/contest/426/problem/C
 3 最多交换k个数的顺序,求a[i]的最大连续和
 4 爆解
 5 思路:Lets backtrack interval that should contain maximal sum. 
 6 To improve it we can swap not more then K minimal elements
 7  in fixed interval to not more K maximal elements not 
 8  contained in our interval. As n is quite little we can 
 9  do it in any way. Author solution works O(n3?*?log(n)).
10 */
11 #include <iostream>
12 #include <vector>
13 #include <string.h>
14 #include <algorithm>
15 #include <queue>
16 #include <set>
17 
18 using namespace std;
19 int sum[210][210],a[210];//sum[i][j]保存从i到j的和
20 int main(){
21     int n,k,i,j,o,ans;
22     cin>>n>>k;
23     for(i=0;i<n;i++) cin>>a[i];//输入
24     memset(sum,0,sizeof(sum));//清0
25     ans=-5000000;//最值
26     for(i=0;i<n;i++){
27         sum[i][i]=a[i];
28         if(sum[i][i]>ans) ans=sum[i][i];
29         for(j=i+1;j<n;j++){
30             sum[i][j]=sum[i][j-1]+a[j];
31             if(sum[i][j]>ans) ans=sum[i][j];
32         }
33     }
34     priority_queue<int> temp;
35     multiset<int> add;
36     for(i=0;i<n;i++){
37         for(j=i;j<n;j++){
38             for(o=i;o<=j;o++){//查找从i到j为负的最小的k个
39                 if(a[o]<0) temp.push(a[o]);
40                 if(temp.size()>k) temp.pop();
41             }
42             if((j-i+1)==temp.size()){//全为负
43                 sum[i][j]=temp.top();
44                 while(!temp.empty()) temp.pop();//清空
45             }
46             else{
47                 while(!temp.empty()){//清空
48                     sum[i][j]-=temp.top();//将负的移出
49                     temp.pop();
50                 }
51             }
52 
53             add.clear();//清空add
54             //对于非[i,j]部分取k个最大正数
55             for(o=i-1;o>=0;o--){
56                 if(a[o]>0) add.insert(a[o]);
57                 if(add.size()>k) add.erase(add.begin());
58             }
59             for(o=j+1;o<n;o++){
60                 if(a[o]>0) add.insert(a[o]);
61                 if(add.size()>k) add.erase(add.begin());
62             }
63             while(!add.empty()){
64                 sum[i][j]+=*add.begin();
65                 add.erase(add.begin());
66             }
67             if(sum[i][j]>ans) ans=sum[i][j];//更新ans
68         }
69     }
70     cout<<ans<<"\n";
71     return 0;
72 }
复制代码



相关文章
|
1月前
leetcode-485:最大连续1的个数
leetcode-485:最大连续1的个数
21 0
【剑指offer】-最小K个数-28/67
【剑指offer】-最小K个数-28/67
|
4月前
【LeetCode】1171. 从链表中删去总和值为零的连续节点、面试题 02.05. 链表求和
目录 1171. 从链表中删去总和值为零的连续节点 面试题 02.05. 链表求和
27 0
|
2月前
|
算法 测试技术 C#
C++前缀和算法的应用:得到连续 K 个 1 的最少相邻交换次数 原理源码测试用例
C++前缀和算法的应用:得到连续 K 个 1 的最少相邻交换次数 原理源码测试用例
|
4月前
|
算法
【算法专题突破】双指针 - 最大连续1的个数 III(11)
【算法专题突破】双指针 - 最大连续1的个数 III(11)
16 0
|
7月前
|
Cloud Native Go
801. 使序列递增的最小交换次数:动态规划
这是 力扣上的 801. 使序列递增的最小交换次数,难度为 困难。
|
8月前
剑指offer 41. 最小的k个数
剑指offer 41. 最小的k个数
45 0
LeetCode 485. 最大连续 1 的个数 - 暴力法
定义两个变量 thisSum 每次遍历中的最大值 maxSum 返回值,所有遍历结果中的最大值
|
10月前
|
存储
Leetcode——485. 最大连续 1 的个数
文章目录 1、题目 2、滑动窗口 3、一次遍历(官方题解)
Leetcode——485. 最大连续 1 的个数
|
存储
【每日一题Day60】LC1703得到连续 K 个 1 的最少相邻交换次数 | 中位数贪心
局部最优:x位于区间[p[0],p[k−1]]内部时【无论位于哪个位置】,到p[0]和p[k−1]的距离是定值p[k−1]−p[0],因此应使x xx位于所有区间的内部即中位数,使x xx到所有区间的距离为定值,此时能够达到全局最优
69 0
【每日一题Day60】LC1703得到连续 K 个 1 的最少相邻交换次数 | 中位数贪心