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