POJ 1010 解题报告 STAMPS

考察多判。

遍历所有组合，取出最好组合。

上代码。

?

#include <iostream>#include <map>#include <cstring>#include <algorithm>using namespace std;int arrStampType[256];int arrCustomer[256];int arrAnswer[7];  // 0数据长度  1种类  6tie?void showInput();void cal();void calRequest(int iRequest);void judgeBetter(int i, int j, int k, int l);int main (){int iVal;while (1){cin >> iVal;if (cin.eof()){break;}int i = 1;while (iVal){arrStampType[i ++] = iVal;cin >> iVal;}arrStampType[0] = i - 1;i = 1;cin >> iVal;while (iVal){arrCustomer[i ++] = iVal;cin >> iVal;}arrCustomer[0] = i - 1;cal();}return 0;}void cal(){sort(&arrStampType[1], arrStampType + arrStampType[0] + 1);for (int i = 1; i <= arrCustomer[0]; i ++){calRequest(arrCustomer[i]);}return;}void calRequest(int iRequest){memset(arrAnswer, 0, sizeof (arrAnswer));int iSum;for (int i = arrStampType[0]; i >= 1; i --){iSum = arrStampType[i];if (iSum > iRequest){// 第一个数，可以省略// iSum -= arrStampType[i];continue;}if (iSum == iRequest){// 判断种类judgeBetter(i, -1, -1, -1);continue;}for (int j = i; j >= 1; j --){iSum += arrStampType[j];if (iSum > iRequest){iSum -= arrStampType[j];continue;}if (iSum == iRequest){judgeBetter(i, j, -1, -1);iSum -= arrStampType[j];continue;}for (int k = j; k >= 1; k --){iSum += arrStampType[k];if (iSum > iRequest){iSum -= arrStampType[k];continue;}if (iSum == iRequest){judgeBetter(i, j, k, -1);iSum -= arrStampType[k];continue;}for (int l = k; l >= 1; l --){iSum += arrStampType[l];if (iSum > iRequest){iSum -= arrStampType[l];continue;}if (iSum == iRequest){judgeBetter(i, j, k, l);iSum -= arrStampType[l];continue;}iSum -= arrStampType[l];break;}iSum -= arrStampType[k];}iSum -= arrStampType[j];}iSum -= arrStampType[i];}if (arrAnswer[0] == 0){cout << iRequest << " ---- none" << endl;return;}if (arrAnswer[6] == 1){cout << iRequest << " (" << arrAnswer[1] << "): " << "tie" << endl;return;}cout << iRequest << " (" << arrAnswer[1] << "):";for (int i = arrAnswer[0] - 1; i >= 2 ; i --){cout << " " << arrAnswer[i];}cout << endl;return;}void judgeBetter(int i, int j, int k, int l){int iTpCnt = 4;bool bBetter = false;if (l == -1){iTpCnt --;if (k == -1){iTpCnt --;if (j == -1){iTpCnt --;}}}int iStmpCnt = iTpCnt;if (j != -1){if (i == j){iTpCnt --;}if (k != -1){if (j == k){iTpCnt --;}if (l != -1){if (k == l){iTpCnt --;}}}}// 比现有答案的种类多if(iTpCnt > arrAnswer[1]){bBetter = true;}// 种类一样多else if (iTpCnt == arrAnswer[1]){// 比现有答案的张数少if (iStmpCnt < arrAnswer[0] - 2){bBetter = true;}// 张数一样多else if (iStmpCnt == arrAnswer[0] - 2){// 比现有答案的最大面额大if (arrStampType[i] > arrAnswer[2]){bBetter = true;}// 最大面额一样else if (arrStampType[i] == arrAnswer[2]){// 出现tiearrAnswer[6] = 1;}}}if (bBetter){arrAnswer[1] = iTpCnt;arrAnswer[0] = 2 + iStmpCnt;arrAnswer[2] = arrStampType[i];if (j != -1){arrAnswer[3] = arrStampType[j];if (k != -1){arrAnswer[4] = arrStampType[k];if (l != -1){arrAnswer[5] = arrStampType[l];}}}arrAnswer[6] = 0;}}

?