1409 : 签到题

时间限制:1 Sec 内存限制:64 MiB 提交:53 正确:9

提交 状态 论坛

题目描述

NQ的签到题,题意十分简洁明了:

给定一个元素个数为 n 的整型数组

选择 2 个区间,分别求和得到 a, b 且 a > 0, b > 0, 同时,如果其它任意一个区间的和为 e, 则需要满足 min(a, b) ≥ e

再选择 2 个区间, 分别求和得到 c, d 且 c < 0,d < 0, 同时,如果其它任意一个区间的和为 f,则需要满足 max(c, d) ≤ f

数据保证一定可以找到满足条件的 a, b, c, d

最后,输出 a * b 和 c * d 的最大公约数即可。

输入描述

第一行输入一个整数 n   4 ≤ n ≤ 3000

第二行输入 n 个整数,每个整数的绝对值小于等于 106,且至少存在两个正数,两个负数。

输出描述

按题目要求找到 a, b, c, d,输出 gcd(a * b, c * d)即可。

为了再次降低难度,下图为本题的其中一种实现方式,出题人保证下述代码只要敲打正确就一定可以运行出正确的结果:

# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

typedef long long LL;
const int maxn = 3e3 + 5;
int num[maxn];
vector<LL> zhengshu, fushu; // 为了对新生更加友好,这里特意用拼音命名

LL get_sum(int i, int j)
{
    LL sum = 0;
    while (i <= j)
        sum += num[i++];
    return sum;
}

LL gcd(LL a, LL b)
{
    while (b) {
        LL t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> num[i];
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            LL x = get_sum(i, j);
            if (x > 0)
                zhengshu.push_back(x);
            else if (x < 0)
                fushu.push_back(x);
        }
    sort(zhengshu.begin(), zhengshu.end());
    sort(fushu.begin(), fushu.end());
    LL a = zhengshu[zhengshu.size() - 1], b = zhengshu[zhengshu.size() - 2];
    LL c = fushu[0], d = fushu[1];
    cout << gcd(a * b, c * d) << endl;
    return 0;
}

样例输入

6
2 2 -1 -1 2 -1

样例输出

2

来源

逆乾