漏掉的账目明细

漏掉的账目明细

时间： 1ms        内存：128M

描述：

某财务部门结账时发现总金额不对头。很可能是从明细上漏掉了某1笔或几笔。如果已知明细账目清单，能通过编程找到漏掉的是哪1笔或几笔吗？
如果有多种可能，则输出所有可能的情况。

输入：

用户输入的第一行是：有错的总金额。
接下来是一个整数n，表示下面将要输入的明细账目的条数。
再接下来是n行整数，分别表示每笔账目的金额。

输出：

所有可能漏掉的金额组合。每个情况1行。金额按照从小到大排列，中间用空格分开。

示例输入：

6
5
3
2
4
3
1

示例输出：

1 3 3
1 2 4
3 4

提示：

参考答案（内存最优[760]）：

#include <stdio.h>
#include <math.h>
int main(){
	double a,b,c,p,s,r;
	while(scanf("%lf%lf%lf",&a,&b,&c)==3){
		if(a==0.0 || b==0.0 || c==0.0)
			r=0.0;
		else{
			p=(a+b+c)/2;
			s=sqrt(p*(p-a)*(p-b)*(p-c));
			r=2*s/(a+b+c);
		}
		printf("The radius of the round table is: %.3lf\n",r);
	}
	return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
int have[100]={0};
int cost[100];
int n;
int te;
int count;
int test[100]={0};
char pri[100][100];     
int comp(const void*a,const void*b);
int main()
{	
	void dfs(int,int);
	int i;
	int money;
	cin>>money;
	cin>>n;
	int sum=0;
	for(i=0;i<n;i++)
	{	
		cin>>cost[i];
		have[i]=1;
		sum+=cost[i];
	}
	te=0;
	count=0;
	int j,k;
	dfs(sum-money,n-1);
	for(i=0;i<count;i++)
	{	
		bool can=true;
		for(k=0;k<i;k++)
		{
			if(strcmp(pri[i],pri[k])==0)
				can=false;
		}
		if(can)
		{
			j=0;
			while(pri[i][j]!=0)
			{
				cout<<int(pri[i][j]);
				if(pri[i][j+1]!=0)cout<<' ';
				j++;
			}
			cout<<endl;
		}	
	}
	return 0;
}
void dfs(int money,int last)
{	
	int i;
	int a[100];
	for(i=last;i>=0;i--)
	{
		if(money-cost[i]>0)
		{	
			test[te++]=cost[i];
			dfs(money-cost[i],i-1);
			test[--te]=0;
		}
		else
		{
			if(money-cost[i]==0)
			{
				int j;
				test[te++]=cost[i];
				for(j=0;j<te;j++)
				{
					a[j]=test[j];
				}
				qsort(a,te,sizeof(int),comp);
				for(j=0;j<te;j++)
				{	
					pri[count][j]=a[j];
				}
				count++;
				test[--te]=0;
			}
		}
	}
}
int comp(const void*a,const void*b)
{
	return *(int*)a-*(int*)b;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。