首页 > 试题广场 >

元素方碑

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


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

\hspace{23pt}\bullet\,正面轰击：雷元素从第 i-1 块流向第 i+1 块，使 a_{i-1} 减 1、a_{i+1} 加 1；
\hspace{23pt}\bullet\,反面轰击：雷元素从第 i+1 块流向第 i-1 块，使 a_{i+1} 减 1、a_{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}。
算法知识视频讲解
添加回答
牛客242693846号头像 牛客242693846号
列表分成两组，一组为奇数项，一组为偶数项，奇数项偶数项长度都大于0，不然列表是单个元素，直接YES
要满足两个条件，奇数项均值等于偶数项均值，且所有总和的均值为整数才能得到结果
其余均不可。
发表于 2025-07-14 15:35:30 回复(0)
Java
BraveCoder头像 BraveCoder 
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)
逆天邪神扎席德鲁头像 逆天邪神扎席德鲁
# 所有的能量只能在隔一个方尖碑上流动。1,3,5,7... / 2,4,6,8...
# 并且可以操作任意次，每次加减1，所以只要保证整个数组的和是n的倍数，并且上面两组的平均数相等
# 先判断所有和是否是n倍数。
g = int(input())
for _ in range(g):
    n = int(input())
    l = list(map(int,input().split()))
    if (len(l) == 1):
        print("YES")
        continue
    elif (sum(l) % n):
        print("NO")
        continue
    else:
        l1 = [x for i,x in enumerate(l) if i % 2 == 0]
        l2 = [x for i,x in enumerate(l) if i % 2 == 1]
        if (sum(l1)/len(l1) == sum(l2)/len(l2)):
            print("YES")
            continue
        else:
            print("NO")
            continue
发表于 2025-11-30 10:57:44 回复(0)
牛客491233788号头像 牛客491233788号
我没看懂题，它的示例和我对能量转移过程的理解，完全对不上
发表于 2025-11-05 17:49:47 回复(1)
Ginkgo_L头像 Ginkgo_L
奇偶组平均相等即可
import sys
def main():
    t=int(input())
    for _ in range(t):
        n=int(input())
        arr=list(map(int,input().split()))
        if sum(arr)%n !=0:
            print("NO")
            continue
        odd=arr[1::2]
        even=arr[0::2]
        if len(odd) and len(even):
            if (sum(odd)/len(odd))!=(sum(even)/len(even)):
                print("NO")
                continue
        print("YES")
if __name__=="__main__":
    main()

发表于 2025-09-25 23:07:06 回复(0)
高兴0615头像 高兴0615
import sys

t = int(input())
for _ in range(t):
    n = int(input())
    num_list = list(map(int, input().split()))

    if len(num_list) <= 1:
        print('YES')
    elif sum(num_list) % len(num_list) != 0:
        print('NO')
    else:
        num_list1, num_list2 = num_list[0::2], num_list[1::2]
        if sum(num_list1) / len(num_list1) != sum(num_list2) / len(num_list2):
            print('NO')
        else:
            print('YES')
   
   
发表于 2025-09-18 17:19:44 回复(0)
C++
icepointboy头像 icepointboy 
#include <iostream>
#include<vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        long long sum = 0;
        vector<int> vec(n);
        for (int i = 0; i < n; i++) {
            cin >> vec[i];
            sum += vec[i];
        }
        if (sum % n != 0) {
            cout << "NO\n";
            continue;
        }
        long long av = sum / n;
        for (int i = 1; i < n - 1; i++) {
            vec[i + 1] += vec[i - 1] - av;
            vec[i - 1] = av;
        }
        if (vec[n - 1] != av)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

发表于 2025-09-14 14:05:25 回复(0)
C++
Jupiter-56头像 Jupiter-56
#include <cstddef>
#include <iostream>
using namespace std;
#include <cstdlib>
#include <vector>
#include <sstream>

int main() {
    int t, n;
    string s;
    cin >> t;
    while (t--) { // 注意 while 处理多个 case
        vector<int> v;
        v.clear();
        cin >> n;
        cin.ignore();
        getline(cin, s);
        istringstream ss(s);
        int sum = 0;
        while(getline(ss, s, ' ')){
            v.push_back(stoi(s));
            sum += stoi(s);
        }
        if(sum % n != 0){
            cout << "NO" << endl;
            continue;
        }
        sum /= n;
        for(int i = 0; i < n - 2; i++){
            v[i + 2] -= sum - v[i];
            v[i] = sum;
        }
        bool b = true;
        for(auto p:v){
            if(p != sum){
                cout << "NO" << endl;
                b =false;
                break;
            }
        }
        if(b){
            cout << "YES" << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")
发表于 2025-08-27 15:30:24 回复(0)
Python3
忧伤的双曲线头像 忧伤的双曲线
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    sum_a = sum(a)
    if sum_a%n==0:
        sum_ji = 0
        for j in range(1,n,2):
            sum_ji += a[j]
        if sum_ji==sum_a//n*(n//2):
            print('YES')
        else:
            print('NO')
    else:
        print('NO')
发表于 2025-08-24 18:10:08 回复(0)
我乃_三转巅峰头像 我乃_三转巅峰
有一个奇怪的点，输入接近极限不早就超1s了吗，都10^9级别了
发表于 2025-08-21 10:11:38 回复(1)
呆瓜不呆头像 呆瓜不呆
#include <iostream>
#include <vector>
using namespace std;
// 1.先判断均分
// 2.从第一个数开始，通过正转移或者逆转移的方式加或减到均数，修改i+2的值
// 3.判断最后两个数是否是均数，如果是，则true,反之false。

bool is_eq(vector<int> v,int u){

    if (v.size()==1) return true;

    for (int i=0; i<v.size()-2; i++) {
        int diff=0;
        if (v[i]!=u) {
            diff=v[i]-u;
            v[i+2]+=diff;
        }
    }

    if(v[v.size()-2]==u && v[v.size()-1]==u ){
        return true;
    }else{
        return false;
    }

}

int main() {
    int n;
    cin>>n;
    while(n--){
        int k;
        cin>>k;
        vector<int> v(k);
        int sum=0,u;
        for(int i=0;i<k;i++){
            cin>>v[i];
            sum+=v[i];
        }
        u=sum/k;

        if (u*k!=sum) {
            cout<<"NO"<<endl;
        }else {

        if(is_eq(v,u)){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
        }
    }

}
发表于 2025-08-04 17:58:33 回复(0)
牛客670403682号头像 牛客670403682号
#include <stdio.h>

void fun(int j,int k,int *a)
{
    //按规则可以推断只有单数角标相互可以相互做数据的转移，只有双数角标可以相互做数据的转移，所以只需要求平均即可知道是否能让能量相等
    int m = 0;//角标从0开始
    int count_m = 0;
    int sum_m = 0;
    int n = 1;//角标从1开始
    int count_n = 0;
    int sum_n = 0;

    while(m < j){
        sum_m += a[m];
        m += 2;
        count_m++;
    }
    while(n < j)
    {
        sum_n += a[n];
        n += 2;
        count_n++;
    }
    if((sum_m / count_m == k) &&(sum_m % count_m == 0) && (sum_n / count_n == k)&& (sum_n % count_n == 0))//只有正好整除才满足可以均分的情况
    {
        printf("YES\n");
    }else{
        printf("NO\n");
    }
}

int main() {
    int t,n,sum,j,k;
    int i = 0;
    scanf("%d", &t);
    int a[100];//n个整数，此处限制100个
   
    //要做t次
    while (t--) {
        i = 0;
        sum = 0;
        scanf("%d", &n);
        j = n;
        while(n--){
            scanf("%d", &a[i]) ;
            i++;
        }
        // printf("%d %d\n",i,n);
          while(i)
            {
                sum += a[i-1];
                i--;
            }
            if((sum % j) != 0)
            {
                printf("NO\n");
            }
            else
            {
                k = sum / j;
                fun( j,k,a);
            }
    }
 return 0;
}
发表于 2025-06-24 12:00:17 回复(0)
提交观点

问题信息

来自：2025年秋招-中国移...
难度：
12条回答 289浏览

热门推荐

相关试题

元素方碑

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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