迅雷笔试题(2018/09/13)

algorithm

1、计算勾股数

计算勾股数 - 后台开发工程师
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
勾股数，是由三个正整数组成的数组；能符合勾股定理 a*a + b*b = c*c ， (a, b, c) 的正整数解。如果 (a, b, c) 是勾股数，它们的正整数倍数，也是勾股数。如果 (a, b, c) 互质，它们就称为素勾股数。给定正整数N，计算出小于或等于N的素勾股数个数。(0 < a <= b <= c <= N)
输入
正整数N
输出
小于或等于N的素勾股数个数
(0 < a <= b <= c <= N)
样例输入
10
样例输出
1
## 解题思路
暴力遍历。。。
## 题解
#include <iostream>
using namespace std;
// gcd求两个数的最大公约数
int gcd(int x, int y) {
    int t;
    while (y) t = x, x = y, y = t % y;
    return x;
}
// 判断三个数是否互质
int isCoprimeNumber(int x, int y, int z) {
    if (gcd(x, y) == 1 && gcd(y, z) == 1 && gcd(x, z) == 1)
        return true;
    return false;
}
int main() {
    int n;
    cin >> n;
    int count = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            for (int k = j; k <= n; ++k) {
                if (i * i + j * j == k * k && isCoprimeNumber(i, j, k))
                    count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

2、红黑积木求和

红黑积木求和 - 后台开发工程师
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
有红黑两种颜色的方块积木，红色代表正数A，黑色代表负数B。选出17块积木排成一排，使得任意相邻7块积木之和都小于0。如何挑选才能使17块积木之和最大，最大值是多少？
输入
正数A，负数B
A和B绝对值小于10000
输出
积木之和的最大值
样例输入
10 -61
样例输出
28
## 解题思路
1、找出7个数之和 < 0 且尽可能大的组合
2、将17个数分为 7 7 3 ，使3的组合最大，即正数尽可能多
Tips：也可以维持一个长度为7的滑动窗口实现，窗口7个数之和 < 0 且尽可能大。
## 题解
#include <iostream>
using namespace std;
int main() {
    int a, b;
    // a为正，b为负
    cin >> a >> b;
    // 正数尽可能多
    int i;
    for (i = 1; i <= 7; ++i) {
        if (a * (7 - i) + b * i < 0)
            break;
    }
    // 7 7 3,让3中的正数尽可能多
    int res;
    if (7 - i >= 3)
        res = a * 3 + (a * (7 - i) + b * i) * 2;
    else
        res = a * (7 - i) + (3 - (7 - i)) * b + (a * (7 - i) + b * i) * 2;
    cout << res << endl;
    return 0;
}