| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
检查过N遍了,还是WA,实在想不出其他什么测试数据了, 大家帮忙跑些测试数据吧,谢谢啦#include <iostream>
#define MAX 1000
using namespace std;
int s_num = 0;
int c_num = 0;
int stamp[MAX];
int cus[MAX];
int res[MAX][5];
int res_num = 0;
int temp[2][5];
void sort1(int array[], int num);
void sort2(int array[MAX][5], int num);
void getAnswer(int array[MAX][5], int num, int dst);
void tryy(int start, int time, int i, int dst);
int getLen(int array[5]);
int getHigh(int array[5]);
int main()
{
int a;
while(cin>>a)
{
s_num = 0;
c_num = 0;
if(a !=0)
{
stamp[s_num++] = a;
while(cin>>a)
{
if(a == 0) break;
else
{
stamp[s_num++] = a;
}
}
while(cin>>a)
{
if(a == 0) break;
else
{
cus[c_num++] = a;
}
}
//cout<<"dst:"<<s_num<<endl;
//第一轮输入结束,开始处理
//对邮票排序
sort1(stamp, s_num);
//cout<<"fd"<<endl;
for(int trav = 0; trav < c_num; trav++)
{
int time = 1;
int ii = 0;
int dst = cus[trav];
int start = 0;
res_num = 0;
for(int i1 = 0; i1 < MAX; i1++)
for(int j1 = 0; j1 < 5; j1++)
res[i1][j1] = 0;
for(int i2 = 0; i2 < 2; i2++)
for(int j2 = 0; j2 < 5; j2++)
temp[i2][j2] = 0;
tryy(start, time, ii, dst);
//对结果按邮票种类数排序
sort2(res, res_num);
/*for(i = 0; i < res_num; i++)
{
for(int j = 0; j <= 4; j++)
cout<<res[i][j]<<" ";
cout<<endl;
}*/
getAnswer(res, res_num, dst);
}
}
else
{
while(cin>>a)
{
if(a == 0) break;
else
{
cus[c_num++] = a;
}
}
for(int i3 = 0; i3 < c_num; i3++)
{
cout<<cus[i3]<<" ---- none"<<endl;
}
}
}
return 0;
}
void tryy(int start, int time, int now, int dst)
{
for(int ii = start; ii < s_num; ii++)
{
//条件入口
if(time <=4 && (stamp[ii] + now) <= dst)
{
temp[0][time] = stamp[ii];
temp[1][time] = ii;
//匹配成功
int to = stamp[ii] + now;
if(to == dst)
{
bool tag[5] = {false, false, false, false, false};
for(int k1 = 1; k1 <= time; k1++)
{
res[res_num][k1] = temp[0][k1];
//cout<<"temp:"<<temp[0][k]<<" ";
}
//算度数
for(int k2 = 1; k2 <= time; k2++)
{
if(tag[k2] == false)
{
res[res_num][0] ++;
for(int kk = k2; kk <= time; kk++)
{
if(temp[1][kk] == temp[1][k2])
{
tag[kk] = true;
}
}
}
}
res_num ++;
}//////////
else
{
tryy(ii ,time + 1, now + stamp[ii], dst);
}
//for(int n1 = 0; n1 <= 1; n1++)
// for(int n2 = 0; n2 <= 4; n2++)
// temp[][n2] = 0;
}
}
}
//插入排序1
void sort1(int array[], int num)
{
for(int pos = 1; pos <= num -1; pos++)
{
int j = pos - 1;
int temp = array[pos];
while(j >= 0 && array[j] > temp)
{
array[j + 1] = array[j];
j -- ;
}
array[j + 1] = temp;
}
}
//插入排序2
void sort2(int array[MAX][5], int num)
{
for(int pos = 1; pos <= num -1; pos++)
{
int j = pos - 1;
int temp1 = array[pos][0];
int temp2 = array[pos][1];
int temp3 = array[pos][2];
int temp4 = array[pos][3];
int temp5 = array[pos][4];
while(j >= 0 && array[j][0] < temp1)
{
array[j + 1][0] = array[j][0];
array[j + 1][1] = array[j][1];
array[j + 1][2] = array[j][2];
array[j + 1][3] = array[j][3];
array[j + 1][4] = array[j][4];
j -- ;
}
array[j + 1][0] = temp1;
array[j + 1][1] = temp2;
array[j + 1][2] = temp3;
array[j + 1][3] = temp4;
array[j + 1][4] = temp5;
}
}
//
void getAnswer(int array[MAX][5], int num, int dst)
{
if(num == 0)
{
cout<<dst<<" ---- none"<<endl;
return ;
}
//round1 得到牌数最少的
int res1[MAX + 1];
int res2[MAX + 1];
int best = array[0][0];
int least = 10;
int largest = 0;
for(int i1 = 0; i1 < num; i1++)
{
if(array[i1][0] == best)
{
int len = getLen((array[i1]));
if(len < least)
{
least = len;
res1[0] =0;
res1[0] ++;
res1[res1[0]] = i1;
}
else if(len == least)
{
res1[0] ++;
res1[res1[0]] = i1;
}
}
}
//cout<<"FF:"<<res1[0]<<endl;
//得到最大的
for(int i2 = 1; i2 <= res1[0]; i2++)
{
int high = getHigh((array[res1[i2]]));
//cout<<"high:"<<high<<endl;
if(high > largest)
{
res2[0] =1;
res2[res2[0]] = res1[i2];
largest = high;
}
else if(high == largest)
{
res2[0] ++;
res2[res2[0]] = i2;
}
}
if(res2[0] > 1)
{
cout<<dst<<" ("<<array[0][0]<<"): tie"<<endl;
}
else if(res2[0] == 1)
{
int pos = res2[1];
//cout<<"pos:"<<pos<<endl;
int len = getLen(array[pos]);
cout<<dst<<" ("<<array[0][0]<<"):";
for(int k = 1; k <= len; k++)
{
cout<<" "<<array[pos][k];
}
cout<<endl;
}
return ;
}
int getLen(int array[5])
{
int num = 0;
for(int i = 1; i<= 4; i++)
{
if(array[i] != 0)
num ++;
}
return num;
}
int getHigh(int array[5])
{
int max = 0;
for(int i = 1; i<= 4; i++)
{
if(array[i] > max)
max = array[i];
}
return max;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator