首页 > 试题广场 >

元素方碑

[编程题]元素方碑
  • 热度指数:6081 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解


\hspace{15pt}菲谢尔在稻妻冒险途中遇到一排神奇的元素方碑,其中第 i 个方碑初始时的能量为 a_i。只要她对第 i 块方碑施放雷元素,就会发生能量转移:

\hspace{23pt}\bullet\,正面轰击:雷元素从第 i-1 块流向第 i+1 块,使 a_{i-1}1a_{i+1}1
\hspace{23pt}\bullet\,反面轰击:雷元素从第 i+1 块流向第 i-1 块,使 a_{i+1}1a_{i-1}1

\hspace{15pt}操作只能在 2\leqq i\leqq n-1 的方碑上进行,且任何时刻所有方碑能量 a_{i} 必须保持非负。
\hspace{15pt}当所有方碑的能量 a_1,a_2,\dots,a_n 全部相等时,菲谢尔即可开启隐藏宝箱。
\hspace{15pt}菲谢尔可以无限次进行操作。请判断,她是否一定能够让所有方碑能量相等。

输入描述:
\hspace{15pt}第一行输入一个整数 t\left(1\leqq t\leqq 10^4\right)——测试用例组数。 
\hspace{15pt}对于每组测试数据:
\hspace{23pt}\bullet\,第一行输入一个整数 n\left(1\leqq n\leqq 2\times10^5\right)——方碑数量;
\hspace{23pt}\bullet\,第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1\leqq a_i\leqq 10^9\right)——初始能量。

\hspace{15pt}除此之外,保证单个测试文件中全部测试用例的 n 之和不超过 2\times10^5


输出描述:
\hspace{15pt}对每组测试数据,在一行上输出 \texttt{YES}\texttt{NO},表示能否通过若干次操作使所有方碑能量相等。
示例1

输入

8
3
3 2 1
3
1 1 3
4
1 2 5 4
4
1 6 6 1
5
6 2 1 4 2
4
1 4 2 1
5
3 1 2 1 3
3
2 4 2

输出

YES
NO
YES
NO
YES
NO
NO
NO

说明

\hspace{15pt}在第一组样例中: 
\hspace{23pt}\bullet\,对于数组 \{3,2,1\},先对下标 i=2 正面轰击一次,得到 \{2,2,2\},能量已全部相等;
\hspace{23pt}\bullet\,对于数组 \{1,2,5,4\},可依次正面轰击 i=3,反面轰击 i=2,最终得到 \{3,3,3,3\}
\hspace{23pt}\bullet\,对于数组 \{2,4,2\},无论如何操作,总能量 \sum a_i 不是 n 的倍数,因此无法全等,答案为 \texttt{NO}
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int round = in.nextInt();

        for (int i = 0; i < round; i++) {
            int n = in.nextInt(); // 表示方碑数量
            long oddSum = 0;     
            long evenSum = 0;     

            result: {
                // 处理n=1的边界情况:单个方碑已相等
                if (n == 1) {
                    in.nextLong();
                    System.out.println("YES");
                    break result;
                }

                // 读取n个方碑的能量,按1-based索引分奇偶位求和
                for (int j = 1; j <= n; j++) {
                    long num = in.nextLong(); 
                    if (j % 2 == 1) {
                        oddSum += num;
                    } else {
                        evenSum += num;
                    }
                }

                // 条件1:总能量必须能被n整除(否则无法均分)
                long total = oddSum + evenSum;
                if (total % n != 0) {
                    System.out.println("NO");
                    break result;
                }

                // 计算奇位数量和偶位数量
                int oddCount = (n + 1) / 2; // 1-based索引的奇位数量(如n=3→2,n=4→2)
                int evenCount = n / 2;      // 1-based索引的偶位数量(如n=3→1,n=4→2)

                // 条件2:奇位总和/奇位数量 == 偶位总和/偶位数量(均等于avg)
                // 注:因total%n==0,且oddSum/oddCount == evenSum/evenCount,故必能整除(推导见前文)
                if (oddSum / oddCount == evenSum / evenCount) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
        in.close();
    }
}

发表于 2025-08-27 20:57:51 回复(0)