CF262B Roma and Changing Signs

洛谷题面

题目大意

一个人要统计他所在公司的总收入并且他想使总收入达到最大,收入写在一条清单上,总收入是清单上所有数之和。

他有 \(k\) 次操作的机会,每次操作可以将某个数一个数变成其相反数,例如 \(1\) 变成 \(-1\) (注意,他必须严格执行 \(k\) 次)问总收入最大是多少?

题目分析

将数组从小到大排序后:

在前 \(m\) 个数中,我们取出负数并取反,若 \(\ge0\) 则马上退出。将这些数取反之后,就能够将 \(\sum\limits_{i=1}^{n}a_i\) 的和变得更大。

\(m\) 将这些负数取反后还有剩余,那么再分类讨论:

  • \(m\) 为偶数,则偶数次操作后 \(a\) 的值不变。

  • \(m\) 为奇数,则只需操作一次就等价于操作 \(m\) 次操作,将最小值取反即可。

代码

细节巨多。。。

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 20;

int n, k;
int vec[MAXN];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++)	cin >> vec[i];
	sort(vec, vec + n);
	int b = 0;
	while (b < n && k--) {
		if (vec[b] >= 0) {
			k++;
			break;
		}
		vec[b++] *= -1;
	}
	if (k < 0)	k = 0;
	sort(vec, vec + n);
	if (vec[0] == 0 || k % 2 == 0) {
		ll sum = 0;
		for (int i = 0; i < n; i++)	sum += vec[i];
		cout << sum << endl;
		return 0;
	}

	vec[0] *= -1;
	ll sum = 0;
	for (int i = 0; i < n; i++)	sum += vec[i];
	cout << sum << endl;
	return 0;
}

推荐这些文章:

2022.1.17

放假好久了,写了几个
上程序:
#include <iostream>using namespace std;
int main(){ int a, x = 1,b=0,c=0,z=0; cin >> a; string k; cin >> k; cout << k; for (int i = 2; i < a; i++) { x += 2 * (2*i - 1); if (x > a) ...

编程统计候选人的得票数。有若干位候选人(n<=10),候选人姓名从键盘输入(候选人姓名不区分大小写,姓名最长为9个字节),若干位选民,选民每次输入一个得票的候选人的名字(姓名最长为9个字节),若选民输错候选人姓名,则按废票处理。程序自动统计各候选人的得票结果,并按照得票数由高到低的顺序排序。最后输出各选票人得票结果和废票信息。

#include <iostream>#include <cstring>using namespace std;struct sign{ char name[20]; int num; int flag;}x[105],y[105],z[105];int main(){ int n; cin>>n; int i,j; for(i=1;i<=n;i++) { cin>>x[i].name; for(j=0;j<strlen(x[i].name);j++) { x[i].name[j]=tolower(x[i].name[j...

pat甲级打卡-1007 maximum subsequence sum

血的教训记得看清楚题目。。。。调试了几个小时
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
// 前缀和
int a[N],s[N];
int k;
int main(){
cin>>k;
for(int i=1;i<=k;i++) cin>>a[i];
for(int i=1;i<=k;i++) s[i]=s[i-1]+a[i];
bool muti=false;
int maxx=-10001;
int x=0...

上海月赛《打印漏斗》

#include <iostream>using namespace std;int main() { int n; cin >> n; for (int i = 1; i <= n - 1 ; i++) { for (int j = 1; j <= i - 1; j++) { cout << ' '; } for (int j = 1; j <= 2 * (n + 1 - i) - 1; j++) { cout << '*';...

Lambda表达式[]中创建的变量,作用域在闭包内,但是生命周期和外部代码块相同

class A:
{
public:
A(int I = 0):i(I){ cout<<"constructor A"<<endl; }
~A() { cout << "distructor A" << endl; }
int getA(){ return i; }
private:
int i;
};

int main()
{
auto func = [a = std::make_unique<A>()]{
return a->...

习题3.5 实现从标准输入每次读入一行文本。然后改写程序,每次读入一个单词。

1.每次读入一个单词

#include<iostream>
#include<string>
using namespace std;
int main(){
string word;
int n=1;
while(cin>>word){
cout<<n<<": "<<word<<endl;
n++;
}
cout<<endl;
system("pause");
return 0;
}

2.每次读入一行文本...

只能买3个物品 尽可能花光钱

#include<bits/stdc++.h>
using namespace std;
int num, sum,sum1=0,count1 =0, r;
int a[100];
vector<int>vec;

int main() {
for (int i = 0; i < 100; i++) {
cin >> a[i];
// cout << "a[i]" << a[i] << endl;
count1++;
if (cin...

2.从一堆数种取出所有众数,输出中间的那个,如果有偶数个众数,输出中间两个的平均值

#include<bits/stdc++.h>
using namespace std;
int num, count1,count2,sum;
int temp = 0,temp1 = 0;
int a[100],b[100];
int* p;
void fun(int b[]) {
for (int i = 0; i < 100; i++) {
b[i] = 0;
}

}
vector<int>vec;
vector<int>::iterator it;
int main() {
while...

[二分法]求解递增序列中与x最接近元素问题

#include <iostream>
using namespace std;

int main(){
int i,mid,m,n,ask;
int a[100000];
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i];
}
cin>>m;
for(i=1;i<=m;i++){
cin>>ask;
if(ask<a[1]){
cout<<a[1]...

C++中控制cout输出的函数——1.setprecision(int n)

setprecision(int n)对之后的cout数字输出生效,将设置输出数字小数精度为n位,对多余的小数位数四舍五入。与fixed搭配使用可在输出数字的小数精度小于n时在小数末尾添加0;
示例代码:
#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
double d=1.98765432,s=1.11111111,f=1;

cout<<d<<endl<<s<<endl
<<...

文章标题:CF262B Roma and Changing Signs
文章链接:https://www.dianjilingqu.com/4232.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>