UVa 10125 Sumsets
解題策略
這題的解法很直接，要找d=a+b+c用四層迴圈下去跑a,b,c,d就好了 XDDDD
我犯了幾個錯誤
- 要找最大符合d (意思是數列中可能出現好幾個符合要求的解)，所以迴圈應該由最大元素往下找，第一個找到的解就是答案，我一開始由最小元素往上遞增尋找，拿了WA。
- 沒找到解就回傳0，殊不知0也有可能是解: 0 = -5 + 3 + 2，這裡也吃了一個WA，所以我後來改回傳 INT_MAX 作為無解。
是比較需要小心的地方。
官網論壇上的(a+b)=(d-c)法，方法複雜很多，卻沒有比較快。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * UVa 10125 Sumsets (AC) | |
| * Author: chchwy | |
| * Last Modified: 2010.03.18 | |
| */ | |
| #include<iostream> | |
| #include<vector> | |
| #include<algorithm> | |
| using namespace std; | |
| int find(vector<int>& set) | |
| { | |
| for (int d = set.size() - 1; d >= 0; --d) // find the largest d | |
| for (int a = 0; a < set.size(); ++a) | |
| for (int b = a + 1; b < set.size(); ++b) | |
| for (int c = b + 1; c < set.size(); ++c) | |
| if ( (set[d] == set[a] + set[b] + set[c]) && | |
| a != d && b != d && c != d ) | |
| return set[d]; | |
| return INT_MAX; | |
| } | |
| int main() | |
| { | |
| #ifndef ONLINE_JUDGE | |
| freopen("10125.in", "r", stdin); | |
| #endif | |
| int numElement; | |
| while (cin >> numElement) | |
| { | |
| if (numElement == 0) | |
| break; | |
| /* input */ | |
| vector<int> set(numElement); | |
| for (int i = 0; i < numElement; ++i) | |
| cin >> set[i]; | |
| sort(set.begin(), set.end()); | |
| /* find d = a + b + c */ | |
| int d = find(set); | |
| if ( d == INT_MAX ) | |
| cout << "no solution\n"; | |
| else | |
| cout << d << "\n"; | |
| } | |
| return 0; | |
| } |
留言
張貼留言