【一级讲解】这是水题——VECTOR与贪心（这是水贴）

这是水题

Time Limit: 1 Sec Memory Limit: 128 MB

Description

xyr最近很喜欢尝试把整数n拆分若干个不相等斐波那契数（f（0）=1，f（1）=1），每次拆分成功就会说一句“xufu1e”；
xyr当然知道要怎么拆，但是现在他想考考你？

Input

输入只有一个整数n（n<196418）

Output

若n不能被拆分则输出“N0”；
否则输出两行
第一行为“xufu1e”
第二行输出若干个不相等的数a[i]
表示f[a[1]]+f[a[2]]+…f[a[m]]==n且a[i]>a[j];(f[k]表示第k个斐波那契数)
若，有多组答案，则使位置靠前的数字金可能大

Sample Input

6

Sample Output

xufu1e

4 1

---

问题分析：

是的，这道题目和斐波那契的拆分——栈与贪心是母子题，如果你不懂这道题的核心算法，可以先移步去看下斐波那契的拆分——栈与贪心先，由于上一题有详细的题解，这里就不重复啰嗦啦。这一题与上一题不同的是，先挖了一个坑，不告诉你任意正整数都能被拆分，其次是要输出的是项数而不是值。下面就不废话，直接贴上代码。这次用vector就好 不用栈

---

AC代码：

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

const int N=200000;
bool mark[N];
int index[N];

int main()
{
	int fibo[45];
	fibo[0]=fibo[1]=1;
	index[1]=1;
	mark[1]=1;
	
	int i;
	for ( i=2; ; ++i )
	{
		fibo[i] = fibo[i-1]+fibo[i-2];
		if ( fibo[i] > N )
			break;
		mark[fibo[i]]=1;
		index[fibo[i]]=i;
	}
	
	int n;
	cin>>n;
	
	vector<int> f;
	if ( mark[n] )
		f.push_back(n);
	else
	{
		for ( i=n-1; i>=1; --i )
		{
			if ( mark[i] && n>0 )
			{
				f.push_back(i);
				n -= i;
				i = n+1;
			}	
			if ( n==0 )	break;
		}
	}
	
	cout << "xufu1e" << endl;
	cout << index[f[0]];
	int len=f.size();
	for ( i=1; i<len; ++i )
		cout << " " << index[f[i]];
	putchar('\n');
	
	return 0;
}