问题描述
鸡哥在“无尽的夏日”购物节上看中了一系列的商品，这些商品的价格各不相同。然而，鸡哥的购物车有一条特殊的规则：购物车中的商品数量必须是偶数个。
鸡哥希望在满足购物车规则的前提下，选择总价值最高的商品。他将商品的价格列表给了你，希望你能帮他计算出他能购买到的商品的最高总价值是多少。
输入格式
第一行包含一个整数N(2≤N≤10⁵),表示商品的数量。
第二行包含N个整数，表示每个商品的价格A₃(-10⁹≤A;≤10⁹)。
输出格式
输出一行，表示鸡哥能购买到的商品的最高总价值。
样例输入
5
12345
样例输出
14
运行限制
语言
最大运行时间
最大运行内存
C
1s
256M
C++
1s
256M
我的答案：第一版本连编译都没通过
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
int main(){
int N=0,sum=0;
cin >> N;
vector<LL> a[N];//在这发现要用方括号
for(int i=0;i<N;i++){
cin >> a[i];
}
if(N%2!=0){
sort(a.begin(),a.end()+1);//忘了sort是升序还是降序了
for(int j=0;j<a.size();j++){
sum=sum+a[j+1];
}
}else{
for(int k=0;k<N;k++){
sum=sum+a[k];
}
}
cout << sum;
}错误原因：
-
读取向量元素时使用
a[i]而不是a(i)。a(i)的语法在 C++ 中是不正确的，应当使用方括号[]以访问向量的元素。 -
在
sort函数调用中，a.end()+1是不正确的。sort函数的范围是左闭右开的，因此应当直接使用a.begin()到a.end()作为参数。如果你想要排序整个向量，应该使用sort(a.begin(), a.end())。 -
在处理
sum时，你在if(N%2!=0)分支中的循环中使用了a(j+1)，这将导致越界访问，因为j+1在循环的最后一次迭代时会超出向量的最大索引。应当使用a[j]来累加向量中的元素。 -
关于
sort函数的默认行为，它是按照升序排序的。如果你需要按照降序排序，可以使用sort的第三个参数，比如sort(a.begin(), a.end(), greater<LL>())。
修改后的代码：我以为对了还是错了
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
int main() {
int N = 0;
LL sum = 0; // 使用 LL 来保持一致性，避免在大数相加时可能的溢出
cin >> N;
vector<LL> a(N);
for (int i = 0; i < N; i++) {
cin >> a[i]; // 使用方括号访问向量元素
}
if (N % 2 != 0) {
sort(a.begin(), a.end()); // 使用标准的 sort 函数排序
for (int j = 0; j < a.size(); j++) {
sum += a[j]; // 正确累加元素
}
} else {
for (int k = 0; k < N; k++) {
sum += a[k];
}
}
cout << sum;
return 0;
}
错误原因没看到商品价格可能是负数，以后要对题目条件仔细看，也暴露出本人的思维不够严谨
。
正确答案：
解题思路：
源代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll sp = 0;
int mn = -1e9 - 1, mp = 1e9 + 1, np = 0;
int n; cin >> n;
for (int i = 0; i < n; i += 1) {
int el; cin >> el;
if (el > 0) {
if (mp > el) {
mp = el;
}
sp += el;
np += 1;
} else if (mn < el) {
mn = el;
}
}
if (np % 2) {
sp = max(sp - mp, sp + mn);
}
cout << sp << '\n';
return 0;
}
我的理解：
一、信息（题目的有用信息）
- 商品数量要求：购物车中的商品数量必须是偶数。
- 价格正负：商品价格可能为正也可能为负。
- 总价值最大化：目标是使购物车中的商品总价值最大。
二、分析（包括每个信息的作用和思考过程）
- 贪心策略：首先，优先选择价格为正的商品，因为这会直接增加总价值。
- 处理奇数数量的正价商品：如果正价商品的数量是奇数，我们需要决定是移除一个正价商品还是添加一个负价商品来满足偶数数量的要求。
- 变量初始化和维护：
sp（购物车商品总价值）np（购物车商品数量）mn（负价商品中的最大值）mp（正价商品中的最小值）
三、算法设计
- 初始化：设置初始变量，包括商品总价值、商品数量、正价商品的最小值、负价商品的最大值。
- 遍历商品：对于每个商品价格进行判断：
- 如果价格大于0，加入购物车，更新总价值和商品数量，同时更新最小正价商品值。
- 如果价格小于等于0，更新最大负价商品值。
- 调整购物车：如果购物车中商品数量为奇数，比较移除一个最小正价商品和添加一个最大负价商品的情况，选择能使总价值最大的方案。
- 输出结果：最后输出购物车商品的最高总价值。
四、代码实现（用C++）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll sp = 0;
int mn = -1e9 - 1, mp = 1e9 + 1, np = 0;
int n; cin >> n;
for (int i = 0; i < n; i += 1) {
int el; cin >> el;
if (el > 0) {
if (mp > el) {
mp = el;
}
sp += el;
np += 1;
} else if (mn < el) {
mn = el;
}
}
if (np % 2) {
sp = max(sp - mp, sp + mn);
}
cout << sp << '\n';
return 0;
}
五、实现代码过程中可能遇到的问题
- 整数溢出：由于商品价格范围很大，必须使用足够大的整数类型来避免溢出（如
long long）。 - 理解正负价值商品的策略：理解负价商品可能带来的总价值增加是问题的关键。
- 正确选择最小正价商品和最大负价商品：要正确维护这两个变量，这对于算法能否得到正确结果至关重要。
上述算法的时间复杂度为 O(N)，因为它通过单次遍历所有商品来实现，这使得它适合处理大量数据的情况。
