C++程序练习-2747:数字方格

描述

如上图，有3个方格，每个方格里面都有一个整数a1，a2，a3。已知0 <= a1, a2, a3 <= n，而且a1 + a2是2的倍数，a2 + a3是3的倍数， a1 + a2 + a3是5的倍数。你的任务是找到一组a1，a2，a3，使得a1 + a2 + a3最大。

输入
输入的第一行是一个数t，表示测试数据的数目。接下来的t行，每行给出一个n (0 <= n <= 100)的值。
输出
对于每一个n的值，输出a1 + a2 + a3的最大值。
样例输入
2
0
3
样例输出
0
5

思路：

枚举，尽量缩小范围

解法：没考虑太多，直接写的

//冰非寒([e-mail])
//252kB 70ms 619 B G++ 
#include <iostream>
using namespace std;
int main(){
    int i,j,k,n,cases,sum;
    std::cin>>cases;
    while(cases --){
        std::cin>>n;
        sum = 0;
        for(i = 0;i <= n;i ++){
            for(j = 0;j <= n;j ++){
                if((i + j) % 2 == 0)
                for(k = 0;k <= n;k ++){
                    if((j + k) % 3 == 0 && (i + j + k) % 5 == 0){
                        if((i + j + k) > sum){
                            sum = i + j + k;
                        }
                    }
                }
            }
        }
        std::cout<<sum<<std::endl;
    }
}

优化解法：

//冰非寒([e-mail])
//256kB 0ms 872 B G++ 
#include <iostream>
using namespace std;
//function
int maxsum(int);
//main function
int main(){
    int cases,n,k;
    cin>>cases;
    while(cases --){
        cin>>n;
        cout<<maxsum(n)<<endl;
    }
    return 0;
}
int maxsum(int n){
    int k = n * 3 - n * 3 % 5;
    for(int s(k);s >= 0;s -= 5){
        for(int a(n);a >= 0;-- a){
            if(s - a > 2 * n || s - a < 0){
                break;
            }
            for(int b(n);b >= 0;-- b){
                if(s - a - b <= n && s - a - b >= 0){
                    if(((s - a) % 2 == 0 && (s - b) % 3 == 0)
                        ||((s - a) % 3 == 0 && (s - b) % 2 == 0)
                        ){
                        return s;
                    }
                }else{
                    break;
                }
            }
        }
    }
    return 0;
}