Description
有$n$个木棍，长度为$1,2,3…n$，现在要从中删掉一些木棍，使得剩下的木棍不能构成三角形，使删掉木棍的数量最少。T组数组，$T \leq 20$
$n \leq 20$
Solution
由于数据范围很小，可以直接暴力求解，依次选取两个数$a,b(a<b)$相加，要知道不能有任何一个数小于这个值，直接删掉$(a,a+b)$范围中的数即可
如果$n$的范围是$1e9$呢？
通过找规律发现我们剩下的数是这样的
$1,2,3,5,8,13,21…$
这是Fibonacci数列!!!!
所以我们只需要找到$\leq n$的Fibonacci数有几个，减去就是答案
可以直接lower_bound注意处理极限数据！！！即$n==1||n==2$的情况
也可手写二分，但是二分貌似常数有点大，又考虑到第$88$个Fibonacci数就爆掉$1e9$了，所以直接便利也完全没问题
Code
暴力版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
bool vis[23];
int main() {
int T;
cin >> T;
for (int i = 1; i <= T; i++) {
int N, ans = 0;
cin >> N;
memset(vis, false, sizeof(vis));
for (int j = 1; j <= N - 1; j++)
if (!vis[j]) {
for (int k = j + 1; k <= N; k++) {
if (!vis[k]) {
for (int l = k + 1; l <= j + k - 1; l++)
if (!vis[l] && l <= N) vis[l] = true, ans++;
break;
}
}
}
printf("Case #%d: %d\n", i, ans);
}
return 0;
}
|
二分+Fib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
typedef unsigned long long uLL;
typedef long long LL;
const LL MOD = 1e18;
using namespace std;
LL f[100];
int main() {
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= 80; i++)
f[i] = f[i - 1] + f[i - 2];
int T;
cin >> T;
for (int i = 1; i <= T; i++){
LL N;
cin >> N;
if (N == 1 || N == 2) {
printf("Case #%d: 0\n", i);
continue;
}
int l = 1, r = 80;
/*手写二分查找
while (l <= r) {
int mid = (l + r) >> 1;
if (f[mid] <= N) l = mid + 1;
else r = mid - 1;
}
int pos = l;
*/
int pos = lower_bound(f, f + 80, N) - f;
if (f[pos] != N) pos--;
printf("Case #%d: %d\n", i, N - pos);
}
return 0;
}
|
Zhiwei Zhang
included in Algorithm