题目链接:Codeforces 425A Sereja and Swaps
题目大意:给出一个长度为n的序列,以及可以交换的次数k,可以在原先的序列中任意交换两个数,然后要求找到一个连续的子序列和最大,输出最大值。
解题思路;枚举区间,o(n^2),然后将区间内最小的数逐个和区间外面最大的数交换。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;
int n, k, a[N], b[N];
void init () {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
}
int solve (int l, int r) {
memcpy(b, a, sizeof(a));
int ans = 0;
for (int i = l; i <= r; i++)
ans += a[i];
int p, q;
for (int i = 0; i < k; i++) {
int bMax = -INF, bMin = INF;
for (int j = 1; j <= n; j++) {
if ((j < l || j > r) && b[j] > bMax) {
bMax = b[j];
p = j;
} else if (j >= l && j <= r && b[j] < bMin) {
bMin = b[j];
q = j;
}
}
int t = bMax - bMin;
if (t <= 0)
break;
ans += t;
swap(b[p], b[q]);
}
return ans;
}
int main () {
init();
int ans = -INF;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++)
ans = max(ans, solve(i, j));
}
printf("%d\n", ans);
return 0;
}
分享到:
相关推荐
[codeforces 1304A] Two Rabbits 整除+模 总目录详见https://blog.csdn.net/mrcrack/article/details/103564004 在线测评地址https://codeforces.ml/contest/1304/problem/A Problem Lang Verdict Time Memory ...
Codeforces 185A - Plant 全测试点49个
题目分析:如果暴力的话显然时间复杂度是 n * n 的,我们应该想办法去优化,比赛的时候想用线段树,但是不会在维护异或的前提下区间加法,也想过用矩阵维护,但丝毫没什么用呀,队友想到了可以按位维护,也就是维护...
解决问题(문제해결) ACM-ICPC凭证,BOJ,CodeForces,Codewars,SCPC,摇动,TopCoder凭证
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
贪心正确性显然:R大的至少可以选则R做为点来用。所以按R升序遍历,每次优先选左边的,能让后边的可选的更多。 用set维护可选的数即可。 这题加了个输出2个方案。 我们考虑最简单的情况:即确定一个序列后,是否有2...
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
怪异的舍入: : 问题845 A.国际象棋锦标赛: : 问题884 B.日语填字游戏反击: : 问题985 A.国际象棋的放置: : 问题1042 A.长凳: : 问题1105 A.塞勒姆和棍子: : 问题1189 B.数字圈: : 问题1255 B.冰箱储物柜: : ...
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...
Codeforces global round 10 codes
codeForces C ++中的Code Force解决方案