洛谷 P4956 [COCI2017-2018#6] Davor

【题目链接】

洛谷 P4956 [COCI2017-2018#6] Davor

【题目考点】

1. 枚举

【解题思路】

星期一筹钱$x$，星期二筹钱$x+k$，…，星期日筹钱$x+6k$。那么一星期筹钱：
${\sum }_{i=0}^6(x+i\cdot k)=7x+21k$，52个星期筹钱：$52(7x+21k)=364(x+3k)$。

解法1：

• 枚举对象：x
• 枚举范围：$1\le x\le 100$
• 判断条件：$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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解法2：

#include
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16