试题 算法训练 Remember the A La Mode有人会做嘛

Question

试题 算法训练 Remember the A La Mode

资源限制
时间限制：1.0s 内存限制：256.0MB

问题描述
　　Hugh Samston经营着一个为今年的ICPC世界总决赛的参与者提供甜点的餐饮服务。他将会提供上面有冰激凌的饼片。为了满足不同的需求，他准备了许多不同的饼片和冰激凌。

　　Hugh希望以一份饼片上一份冰激凌的方式来提供甜点。然而，作为一个商人，他希望能赚到尽可能多的钱。他知道不同种类的饼片和冰激凌组合的价格，也知道那些冰激凌和那些饼片不能组合在一起。

　　Hugh想根据每种饼片和冰激凌的数量，以及之前提到的不同组合的情况，确定他能获得的利润的范围。

输入格式

　　测试数据的输入一定会满足的格式 。

　　输入的第一行包含两个整数P, I，分别表示饼片和冰激凌的种类数。

　　接下来一行包含P个整数，表示每种类型饼片的数量 。

　　接下来一行包含I个整数，表示每种类型冰激凌的数量。

　　接下来P行，每行包含I个实数，表示每种类型饼片和冰激凌组合的结果。
　　如果这种饼片和这种冰激凌可以组合，则为一个(0,10)的实数，表示这种组合的收益。

　　否则，则为-1,表示这两种之间不能组合。

输出格式

　　输出一行，以"(最小收益) to (最大收益)"的方式输出利润的范围。

　　请注意：所有的饼片和冰激凌都必须用完。

样例输入

2 3

40 50

27 30 33

1.11 1.27 0.70

-1 2 0.34

样例输出

91.70 to 105.87

数据规模和约定

0 < P,I <= 50，每种类型饼片或冰激凌数量不超过100。

Answer 1

#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define max_size 110

typedef struct
{
    int n,m;
    float value;//n为饼干的序号,m为冰激凌序号，value为组合的价值
}zh;
long double res=0,max_res=0,min_res=0;
long sum=0;//总份数
float rule(zh a,zh b)//从大到小排序，求最大收益用
{
    return a.value>b.value;
}
float rule1(zh a,zh b)//从小到大排序，求最小收益用
{
    return a.value<b.value;
}
void f(int bk[],int ice[],zh a[],int b,int c)//b排序好后的第几个数 c已完成配对数
{
    if(c>=sum);
    else if(a[b].value<0) f(bk,ice,a,b+1,c);
    else if(bk[a[b].n]==0||ice[a[b].m]==0) f(bk,ice,a,b+1,c);
    else
    {
        if(bk[a[b].n]<ice[a[b].m])
        {
            res=res+a[b].value*bk[a[b].n];
            c=c+bk[a[b].n];
            ice[a[b].m]=ice[a[b].m]-bk[a[b].n];
            bk[a[b].n]=0;
            f(bk,ice,a,b+1,c);
        }
        else
        {
            res=res+a[b].value*ice[a[b].m];
            c=c+ice[a[b].m];
            bk[a[b].n]=bk[a[b].n]-ice[a[b].m];
            ice[a[b].m]=0;
            f(bk,ice,a,b+1,c);
        }
    }
}
int main()
{
    int P,I;
    cin>>P>>I;
    int i,j,num_bk[max_size]={0},num_ice[max_size]={0};
    int bk[max_size],ice[max_size];
    zh combination[3000];
    for(i=1;i<=P;i++)
    {
        cin>>num_bk[i];
        bk[i]=num_bk[i];
        sum=sum+num_bk[i];
    }
    for(i=1;i<=I;i++)
    {
        cin>>num_ice[i];
        ice[i]=num_ice[i];
    }
    int a;
    for(i=1,a=0;i<=P;i++)
    {
        for(j=1;j<=I;j++)
        {
            cin>>combination[a].value;
            combination[a].n=i;
            combination[a++].m=j;
        }
    }
    sort(combination,combination+a,rule);//给收益排序
    f(num_bk,num_ice,combination,0,0);
    max_res=res;
    res=0;
    sort(combination,combination+a,rule1);
    f(bk,ice,combination,0,0);
    min_res=res;
    cout<<fixed<<setprecision(2)<<(long double)min_res<<" to "<<(long double)max_res;//设置输出格式为保留小数点后两位
    return 0;
}
//我这么做只得了20分，我找不到问题在哪