首页 > 试题广场 >

子段和

[编程题]子段和
  • 热度指数:1349 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个序列,问你有没有可能重新排列这个序列使得所有长度小于等于 2 的子区间和不等于 0

输入描述:
第一行一个 n 表示序列长度,接下来一行 n 个数,第 i 个为 a_i,表示序列中的第 i 个数。




输出描述:
一行一个字符串。"YES"表示可能重新排列这个序列使得所有长度小于等于 2 的子区间和不等于 0,反之则输出“NO”。输出不含引号。
示例1

输入

6
34 1345 -3542 -1423 4213 1

输出

YES

说明

不变即可。
示例2

输入

4
1 1 -1 1

输出

NO

说明

无论怎样排列,-1 总和至少 11 相邻,所以总存在一个和为 0 的长度为 2 的子段。
示例3

输入

5
1 5 -1 -5 0

输出

NO

说明

0 的存在使得总有一个长度为 1 的子段和为 0
#include <stdio.h>

int main() {
    long int a, b,d,e,f,g,h,i,q;
    long int c[500000];
    
    scanf("%ld",&a);
    d=a;
    for (a=a,b=0; a>0;a--) {
        scanf("%ld",&c[b]);
        b=b+1;
    }
    for (d=d,e=0; d>0;d-- ) {
        for (g=d,f=0; g>0;g-- ) {
            h=c[e];
            i=c[f];
            if (e==f) {break;
            }else if 
            (h+i==0){
                q=1;
                printf("NO");
                break;
            }
            f=f+1;
        }
        if (q==1) {
            break;
        }
        else if (d==1) {printf("YES");
        break;
        }
        e=e+1;
    }
    return 0;
}
请问为什么调试的结果没问题,但是保存提交后却报错没有输出内容
发表于 2026-03-03 21:04:06 回复(0)
只有以下三种情况:
1. 只要有“0”,则一定不符合要求。
2. 全为正数,或者全为负数,则一定符合要求。
3. 既有正数又有负数,把正数放一起,负数放一起
只要能找到一对正数和负数,绝对值不同,放在交界处即可。
这种情况下:所有数的绝对值全同,不符合要求其它情况均符合要求

速读提示:
按照上述结论,我们只关心“正/负/零”以及(剔除负号后)是否完全相同。
所以无需读成数字,直接读首字符判正负,然后按字符串比对即可。
while (*buf++ != '\n') {}
bool positive = false; // 存在正数
bool negative = false; // 存在负数
bool different = false; // (剔除负号)存在不同的值
if (*buf == '0') { // 遇到0直接结束
    puts("NO");
    return 0;
} else if (*buf == '-') {
    negative = true; // 负数
    buf++; // 剔除负号
} else {
    positive = true; // 正数
}
// 从start到end的字符用来比对
char* start = buf;
while (*buf >= '0') buf++;
char* end = buf;
while (*buf++ == ' ') { // 以空格分割,直到换行结束
    if (different) { // 前面已找到不同,无需读取数字
        if (*buf++ == '0') { // 遇到0直接结束
            puts("NO");
            return 0;
        }
        // 从第2个字符起,跳过所有数字
        while (*buf >= '0') buf++;
    } else { // 前面未找到不同,比对数字
        if (*buf == '0') { // 遇到0直接结束
            puts("NO");
            return 0;
        } else if (*buf == '-') {
            negative = true; // 负数
            buf++; // 剔除负号
        } else {
            positive = true; // 正数
        }
        for (char* ch = start; ch != end; ch++) {
            if (*buf < '0') {
                different = true; // 比预期的短
                break;
            } else if (*buf++ != *ch) {
                different = true; // 找到不同字符
                while (*buf >= '0') buf++;
            }
        }
        if (*buf >= '0') {
            different = true; // 比预期的长
            while (*buf >= '0') buf++;
        }
    }
}
// 有正数有负数且绝对值全部相同,则输出NO,否则,输出YES
puts((!different && (positive & negative)) ? "NO" : "YES");
return 0;


发表于 2026-03-03 04:07:57 回复(0)