蓝桥杯真题——乐乐的序列和（C语言）

问题描述

乐乐在玩一个游戏，她有一排宝石，每个宝石上都刻有一个整数值。她的目标是从中挑选出一些宝石，使得选出的宝石数量为偶数，且这些宝石上的数字总和最大。如果不选任何宝石（即选出宝石数量为 00，也是偶数），总和为 00。请帮助乐乐计算出她能获得的宝石的最大总和是多少。

输入格式

第一行包含一个整数 N，表示宝石的总数。

第二行包含 N 个整数，表示每个宝石上刻的数字。

输出格式

输出一个整数，表示乐乐能获得的宝石的最大总和。

样例输入

4

0 5 3 8

样例输出

16

测评数据规模

$2\leq N\leq 10^{5}$

$10^{-9}\leq$ 数字 $\leq 10^{9}$

运行限制

语言	最大运行时间	最大运行内存
C	1s	256M

解法思路

根据题目要求，第一行输入一个整数N表示的总数即数组元素A的数量，第二行表示数组内元素的数，输出数组内偶数个元素的最大和。将数组内的数从大到小排序，如果正数数量为偶，则答案为所有正数和；如果正数数量为奇数N，则答案为前N-1个数和与N+1个数和中较大者。

解法代码

#include <stdio.h>  
#include <stdlib.h> // 用于qsort函数  // 定义一个函数，返回两个长整型数中的较大值  
long long max(long long x, long long y)
{if (x > y)return x; // 如果x大于y，返回x  else return y; // 否则返回y  
}// 定义一个比较函数，用于qsort排序  
// 此函数比较两个元素（通过指针传入），并返回它们的比较结果  
int cmp_int(const void* elem1, const void* elem2)
{return -(*(int*)elem1 - *(int*)elem2); // 返回一个负数，表示elem1小于elem2，以实现降序排序  
}int main(int argc, char* argv[])
{int N, i; // N表示元素个数，i用于循环  int A[100000]; // 定义一个整型数组A，用于存储输入的N个整数  int sum = 0; // sum用于记录正数的个数  long long sumN = 0; // sumN用于记录所有正数的和，使用long long以防溢出  scanf("%d", &N); // 读取N的值  for (i = 0; i < N; i++)scanf("%d", &A[i]); // 循环读取N个整数到数组A中  qsort(A, N, sizeof(A[0]), cmp_int); // 使用qsort函数对数组A进行降序排序  for (i = 0; i < N; i++){if (A[i] > 0) { sum++; sumN += A[i]; // 如果当前元素为正数，则增加sum并累加sumN}   else break; // 如果遇到非正数，则跳出循环  }// 根据sum（正数的个数）的奇偶性，决定输出sumN（所有正数的和）或是调整后的和  if (sum % 2 == 0)printf("%lld", sumN); // 如果sum为偶数，直接输出sumN  else printf("%lld", max(sumN - A[sum - 1], sumN + A[sum])); // 如果sum为奇数，输出sumN减去最大正数或加上一个负数（但由于数组已排序，A[sum]不存在或不是正数，这里应理解为代码有误，应为A[sum-1]的相反数，但逻辑上应为减去最大正数，即保持原意）  return 0; // 程序结束  
}