首页 > 试题广场 >

灵异背包?

[编程题]灵异背包?
  • 热度指数:6391 时间限制: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。
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        //总数
        int num =Integer.parseInt(st.nextToken());

        st=new StringTokenizer(br.readLine());
        int []arr=new int [num];
        int sum=0;
        for(int i=0;i<num;i++){
            arr[i]=Integer.parseInt(st.nextToken());
            sum+=arr[i];
        }
        Arrays.sort(arr);
        if(sum%2==0){
            System.out.println(sum);
        }else{
            for(int j=0;j<num;j++){
                if(arr[j]%2==1){
                    System.out.print(sum-arr[j]);
                    break;
                }
                if(arr[j]%2==0&&j==num-1){
                    System.out.println(0);
                }
            }
           
        }

    }
}
先都加起来,如果偶数直接输出,排序数组,如果是奇数,从小开始找奇数,减去最小的奇数,如果没有奇数那就是0
发表于 2026-03-31 14:18:57 回复(0)
我的思路是当全部求和后为奇书时,丢弃最后一个奇书。

发表于 2025-10-08 16:49:56 回复(0)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int sum = 0;
        // 标记总和的奇偶性变化(奇数次奇数元素会使总和为奇数,偶数次则为偶数)
        boolean ifOdd = false;
        // 记录数组中最小的奇数(初始值设为整数最大值)
        int minOdd = Integer.MAX_VALUE;
        
        while (n-- > 0) {
            int a = in.nextInt();
            // 如果当前元素是奇数
            if (a % 2 == 1) {
                // 切换总和的奇偶性标记(每加入一个奇数,总和奇偶性改变)
                ifOdd = !ifOdd;
                // 更新最小奇数(保留最小的奇数)
                minOdd = Math.min(a, minOdd);
            }
            sum += a;
        }
        
        // 如果总和最终为奇数(需要调整为偶数)
        if (ifOdd) {
            // 减去最小的奇数,得到最大可能的偶数和
            System.out.print(sum - minOdd);
        } else {
            // 总和已经是偶数,直接输出
            System.out.print(sum);
        }
    }
}

发表于 2025-09-03 14:54:36 回复(0)