| ||||||||||
| 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 | |||||||||
code-style传染计划#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
struct Record {
int a, b, c, d;
int score, kind, cnt, sum;
// 便利 recordList 获取最完美的
// 种类多 → 好
// 种类相同 → 邮票总数少 → 好
// 还相同 → 最大面值高 → 好
// 再相同 → tie
Record() : a(-1), b(-1), c(-1), d(-1) {
kind = 0;
score = 0;
cnt = 0;
sum = 0;
}
Record(int stamps[], int _a) : a(stamps[_a]), b(-1), c(-1), d(-1) {
kind = 1;
cnt = 1;
sum = a;
int maxValue = a;
score = kind * 100000000 + (9 - cnt) * 1000000 + maxValue;
}
Record(int stamps[], int _a, int _b) : a(stamps[_a]), b(stamps[_b]), c(-1), d(-1) {
unordered_set<int> distinctSet;
distinctSet.insert(_a);
distinctSet.insert(_b);
kind = distinctSet.size();
cnt = 2;
sum = a + b;
int maxValue = std::max(a, b);
score = kind * 100000000 + (9 - cnt) * 1000000 + maxValue;
}
Record(int stamps[], int _a, int _b, int _c) : a(stamps[_a]), b(stamps[_b]), c(stamps[_c]), d(-1) {
unordered_set<int> distinctSet;
distinctSet.insert(_a);
distinctSet.insert(_b);
distinctSet.insert(_c);
kind = distinctSet.size();
cnt = 3;
sum = a + b + c;
int maxValue = std::max(std::max(a, b), c);
score = kind * 100000000 + (9 - cnt) * 1000000 + maxValue;
}
Record(int stamps[], int _a, int _b, int _c, int _d) : a(stamps[_a]), b(stamps[_b]), c(stamps[_c]), d(stamps[_d]) {
unordered_set<int> distinctSet;
distinctSet.insert(_a);
distinctSet.insert(_b);
distinctSet.insert(_c);
distinctSet.insert(_d);
kind = distinctSet.size();
cnt = 4;
sum = a + b + c + d;
int maxValue = std::max(std::max(std::max(a, b), c), d);
score = kind * 100000000 + (9 - cnt) * 1000000 + maxValue;
}
void OutputMarch() {
printf("%d (%d):", sum, kind);
if (a >= 0) {
printf(" %d", a);
}
if (b >= 0) {
printf(" %d", b);
}
if (c >= 0) {
printf(" %d", c);
}
if (d >= 0) {
printf(" %d", d);
}
printf("\n");
}
void OutputTie() {
printf("%d (%d): tie\n", sum, kind);
}
};
struct Resolver {
int stamps[100];
int stampsLength;
vector<Record> recordList;
Resolver() : recordList(100) {
}
bool input() {
stampsLength = 0;
while (true) {
if (scanf("%d", &stamps[stampsLength++])==EOF) {
return false;
}
if (stamps[stampsLength - 1] == 0) {
break;
}
}
// 入参排序方便裁剪 (注意有一个0)
sort(stamps, stamps + stampsLength - 1);
return true;
}
void solve(const int need) {
// 需要最多四个邮票;
recordList.clear();
for (int i = 0; i < stampsLength; i++) {
if (stamps[i] == need) {
// 入栈,继续,丢掉儿子
recordList.push_back(Record(stamps, i));
continue;
}
if (stamps[i] > need) {
// 直接break
break;
}
for (int j = i; j < stampsLength; j++) {
if (stamps[i] + stamps[j] == need) {
// 入栈,继续,丢掉儿子
recordList.push_back(Record(stamps, i, j));
continue;
}
if (stamps[i] + stamps[j] > need) {
// 直接break
break;
}
for (int k = j; k < stampsLength; k++) {
if (stamps[i] + stamps[j] + stamps[k] == need) {
// 入栈,继续,丢掉儿子
recordList.push_back(Record(stamps, i, j, k));
continue;
}
if (stamps[i] + stamps[j] + stamps[k] > need) {
// 直接break
break;
}
for (int l = k; l < stampsLength; l++) {
if (stamps[i] + stamps[j] + stamps[k] + stamps[l] == need) {
// 入栈,继续,丢掉儿子
recordList.push_back(Record(stamps, i, j, k, l));
continue;
}
if (stamps[i] + stamps[j] + stamps[k] + stamps[l] > need) {
// 直接break
break;
}
}
}
}
}
// 便利 recordList 获取最完美的
// 种类多 → 好
// 种类相同 → 邮票总数少 → 好
// 还相同 → 最大面值高 → 好
// 再相同 → tie
int cnt, firstPos;
int maxScore = cnt = firstPos = -1;
for (int i = 0; i < recordList.size(); i++) {
if (recordList[i].score > maxScore) {
maxScore = recordList[i].score;
cnt = 1;
firstPos = i;
} else if (recordList[i].score == maxScore) {
cnt++;
}
}
if (cnt == 1) {
recordList[firstPos].OutputMarch();
} else if (cnt > 1) {
recordList[firstPos].OutputTie();
} else {
printf("%d ---- none\n", need);
}
}
};
int main() {
Resolver *resolver = new(Resolver);
while (resolver->input()) {
int need;
while (scanf("%d", &need) != EOF && need != 0) {
resolver->solve(need);
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator