Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

郁闷的wa

Posted by Jason at 2003-05-21 13:25:58 on Problem 1123
```我就是把每个customer需要的features顺着搜一遍,当然重复的不用搜

#include <iostream.h>
#include <stdlib.h>

int minc,maxc,n,m;
int cost[21];
int customer[21][22];
int caseno,i,j,k,s,t;
int sales,costs,margin,feat[21],cust[21],consider[21];
int tempcust[21];
double PI;

int compare(const void*a,const void *b)
{
int x=*((int *)a),y=*((int *)b);
if (x==y) return 0;
if (x<y) return -1;
else return 1;
}

int main()
{

cout.precision(3);
cout.setf(ios::fixed,ios::floatfield);

cin>>caseno;
for (int i=0;i<caseno;i++)
{
cin>>minc>>maxc>>n>>m;
for (j=1;j<=n;j++)
cin>>cost[j];
for (j=1;j<=m;j++)
{
int num;
cin>>num;
customer[j][0]=num;
for (k=1;k<num+2;k++)
cin>>customer[j][k];
}
for (j=1;j<=m;j++)
qsort(customer[j]+1,customer[j][0],sizeof(int),compare);

margin=0;
PI=0;

for (j=1;j<m;j++)
consider[j]=0;

for (j=1;j<=m;j++)
{
if (consider[j]) break;

int tsales,tcosts=0;
consider[j]=1;

for (k=1;k<=customer[j][0];k++)
tcosts+=cost[customer[j][k]];
if (tcosts<minc || tcosts>maxc) break;

for (k=0;k<21;k++) tempcust[k]=0;
tempcust[j]++;
tempcust[0]++;

k=customer[j][0]+1;
tsales=customer[j][k];
for (s=1;s<=m;s++)
{
if (s==j) continue;
if (customer[s][0]>customer[j][0]) continue;

k=1;
int count=0;
for (t=1;t<=customer[s][0];t++)
{
for (;k<=customer[j][0];k++)
if (customer[s][t]==customer[j][k])
{
count++;
break;
}
if (k>customer[j][0]) break;
}
if (count<customer[s][0]) continue;

tempcust[0]++;
tempcust[s]++;
if (count==customer[j][0]) consider[s]=1;
tsales+=customer[s][count+1];
}

double temp=(double)tsales/tcosts;
if (temp>PI)
{
sales=tsales;
costs=tcosts;
PI=temp;
margin=tsales-tcosts;
feat[0]=customer[j][0];
for (k=1;k<=feat[0];k++) feat[k]=customer[j][k];
for (k=0;k<21;k++) cust[k]=tempcust[k];
}

else if (temp==PI)
{
int temp1=tsales-tcosts;
if (temp1>margin)
{
sales=tsales;
costs=tcosts;
PI=temp;
margin=temp1;
feat[0]=customer[j][0];
for (k=1;k<=feat[0];k++) feat[k]=customer[j][k];
for (k=0;k<21;k++) cust[k]=tempcust[k];
}

else if (temp1==margin)
{
if (customer[j][0]<feat[0])
{
sales=tsales;
costs=tcosts;
PI=temp;
margin=temp1;
feat[0]=customer[j][0];
for (k=1;k<=feat[0];k++) feat[k]=customer[j][k];
for (k=0;k<21;k++) cust[k]=tempcust[k];
}

else if (customer[j][0]==feat[0])
{
if (tempcust[0]>cust[0])
{
sales=tsales;
costs=tcosts;
PI=temp;
margin=temp1;
feat[0]=customer[j][0];
for (k=1;k<=feat[0];k++) feat[k]=customer[j][k];
for (k=0;k<21;k++) cust[k]=tempcust[k];
}

}
}
}
}
cout<<"Feature Set "<<i+1<<endl<<PI<<endl<<sales<<endl<<costs<<endl;
for (j=1;j<=feat[0];j++) cout<<feat[j]<<' ';
cout<<endl;
for (j=1;j<21;j++)
if (cust[j]) cout<<j<<' ';
cout<<endl;
}
return 0;
} ```

Followed by: