首页 > 试题广场 >

灵异背包？

[编程题]灵异背包？
  • 热度指数：3516 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定 n 个正整数 \{a_1,a_2,\dots,a_n\}，你可以任选若干个放入“灵异背包”。

\hspace{15pt}要求背包内所有数之和为偶数，且在满足偶数的前提下尽可能大。若一个数也不选，则背包和为 0。

\hspace{15pt}请输出可以获得的最大偶数和。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 10^5\right)。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1\leqq a_i\leqq 2\times10^4\right)。


输出描述:
\hspace{15pt}输出一个整数，表示满足条件的最大偶数和。
示例1

输入

3
2 5 6

输出

8

说明

当灵异背包里面有(2,5,6)，此时总和为2+5+6=13，为奇数，不满足条件。
当灵异背包里面有(2,6)，此时总和为2+6=8，为偶数，且为最大值。
示例2

输入

1
3

输出

0

说明

选择的灵异背包为空，总和为0。
算法知识视频讲解
添加回答
C
人生有三乐头像 人生有三乐
#include <stdio.h>
#include <stdlib.h>

int main() {
    //1+1=2,奇数+奇数=偶数
    //2+2=4.偶数加偶数=偶数
    //3+4=7，偶数加奇数=奇数
    //所以留一个最小的奇数和一个最小的偶数。把剩下的全部加起来看奇数还是偶数，在选一个前面留好奇数或者偶数加上就行,如果选择了偶数，则加上后的结果如果是奇数那么就把剩余的那个最小奇数也加上。如果选择了奇数，则加上后的结果如果是偶数那么就把剩余的那个最小偶数也加

    //大佬的思路：//求和，和为偶则为答案，为奇数减去最小的奇数。好像跟你上面的差不多，更简单了
    int min_oushu;

    int n;
    scanf("%d",&n);
    int* array=malloc(sizeof(int)*n);
    //求和
    int sum=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&array[i]);
        //printf("%d",array[i]);
        //求和
        sum+=array[i];
    }

    //找最小的奇数
    int min_jishu=20000;
    for(int i=0;i<n;i++)
    {
        if(array[i]%2!=0&&array[i]<min_jishu){
            min_jishu=array[i];
        }
    }

    if(sum%2==0)  //是不是偶数
    {
        printf("%d",sum);
    }else {   //为奇数减去最小的奇数
        printf("%d",sum-min_jishu);
    }
    return 0;
}
发表于 2025-10-03 12:24:59 回复(0)
C
牛客478724684号头像 牛客478724684号
#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b){
    int x=*(const int*)a;
    int y=*(const int*)b;
    return (y>x)-(y<x);
}

int main() {
    int n;
    scanf("%d",&n);
    int a[n];
    int ans=0, idx=0;
    for(int i=0; i<n; i++){
        int ai;
        scanf("%d",&ai);
        if(ai%2==0) ans+=ai;
        else{
            a[idx++]=ai;
        }
    }
    qsort(a,idx,sizeof(int),cmp);
    if(idx%2==1){
        for(int i=0; i<idx-1; i++){
            ans+=a[i];
        }
    }
    else if(idx!=0){
        for(int i=0; i<idx; i++){
            ans+=a[i];
        }
    }
    printf("%d",ans);
}
发表于 2025-08-26 06:59:38 回复(0)
提交观点

问题信息

贪心
难度：
2条回答 223浏览

热门推荐

相关试题

灵异背包？

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号