洛谷 P4956 [COCI2017-2018#6] Davor

liuqu1990717 · 2022-10-20 14:11:43 · 个人记录

【题目链接】

洛谷 P4956 [COCI2017-2018#6] Davor

【题目考点】

1. 枚举

【解题思路】

星期一筹钱x，星期二筹钱x+k，...，星期日筹钱x+6k。那么一星期筹钱：

• 判断条件：k=(n/364-x)/3为正整数，即(n/364-x)\%3==0且(n/364-x)/3>0

（不用判断n能否整除364。如果n不能整除364，就无解了。） 题目要求： x 尽可能大，k 尽可能小。 因此x从大到小遍历，找到第一个满足条件的x，根据x求出k，输出x与k，结束程序。

解法2：

• 枚举对象：x, k
• 枚举范围：1\le x \le 100，k从1开始，满足364(x+3k)\le n
• 判断条件：364(x+3k)=n

题目要求： x 尽可能大，k 尽可能小。 因此x从大到小遍历，k 从小到大遍历，找到第一个满足条件的x、k就输出，而后结束程序。

【题解代码】

解法1：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    for(int x = 100; x >= 1; --x)
    {
        if((n/364-x)%3 == 0 && (n/364-x)/3 > 0)
        {
            cout << x << endl << (n/364-x)/3;
            return 0; 
        }
    }
    return 0;
}

解法2：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    for(int x = 100; x >= 1; --x)
        for(int k = 1; 364*(x+3*k) <= n; ++k)
            if(364*(x+3*k) == n)
            {
                cout << x << endl << k;
                return 0;
            } 
    return 0;
}