考察多判。
遍历所有组合,取出最好组合。
上代码。
#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]) { // 出现tie arrAnswer[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; } }
发表评论
-
POJ 1009 解题报告 Edge Detection
2011-12-18 21:13 30271009是痛苦的一题啊 ... -
POJ 1008 解题报告 Maya Calendar
2011-12-16 17:54 1019还是要细心啊,题目不难,历法转换。 AC吧,这么简单 ... -
POJ 1007 解题报告 DNA Sorting
2011-12-15 17:43 909#include <iostream> # ... -
POJ 1006 解题报告 Biorhythms
2011-12-15 17:39 932同理小学生计算题? 还是我没想到什么? #inc ... -
POJ 1005 解题报告 I Think I Need a Houseboat
2011-12-15 17:36 816好吧,小朋友的数学题。 #include <io ... -
POJ 1004 解题报告 Financial Management
2011-12-15 17:34 3058超水一题。 #include <iostream ... -
POJ 1003 解题报告 Hangover
2011-12-15 17:32 1063简单题。 注意不要重复计算。 使用二分查找的思想。 ... -
POJ 1002 解题报告 487-3279
2011-11-25 15:53 988典型的字符串处理问题。 刚开始用的vector,果断超时。题 ... -
POJ 1001 解题报告 Exponentiation
2011-11-25 15:15 1557高精度浮点数计算。 花了我整整一天时间才写好,POJ ...
相关推荐
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1010-STAMPS 解题报告+AC代码
北大ACM-POJ1010 - STAMPS 原比赛(Pacific Northwest 1998)题目的测试数据
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 3720解题报告poj 3720解题报告poj 3720解题报告poj 3720解题报告
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj2828解题报告,希望能帮到志同道合的算法爱好者
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大ACM1316解题报告
Problem 1061 青蛙的约会 poj解题报告。有源码。可直接提交C++实现
ACM Poj Pku 解题报告答案 打包 下载 600多题 史上最全 不是网上乱传的200多题,更不是100多题就挂着10分才能下的题 下了这个 大家也不要浪费分数去下载其它版本的了,基本上都有 共享 一起进步 中国加油 ACMer...
这是我发的第二篇解题报告,写的不怎么的。呵呵!!!!!
北大ACM在线评测系统POJ的题目解题报告。涵盖各种类型的acm题目。值得参考借鉴。打包下载。
不错的资源 收集了网上的一些解题报告 方便同学们学习参考