首页 > 代码库 > ZOJ 3706 Break Standard Weight 解题报告
ZOJ 3706 Break Standard Weight 解题报告
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5009
题目意思:给出两个mass:x 和 y,问如何将其中一个 mass 一分为二(当然分完之后它们的和要等于原来的mass,或x 或 y),使得利用这三个mass 可称的数量最大。输出这个最大数量。
网上参考别人用STL中的set来写,太厉害了!!!考虑到set对于重复的元素只存储一个,那么当三个mass组合的过程中有重复的,它都会自动舍弃有重复的,不需要用if来判断!另外,也有可能其中两个mass是相等的,这时如果各放一边,就只会称到0,即不能称到任何物体!所以预先把0插入,这就是代码中为什么最后要返回 st.size()-1 的原因!!
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <set> 6 using namespace std; 7 8 set<int> st; 9 int cal(int a, int b, int c) 10 { 11 st.clear(); // 每一次都要清空集合里的元素 12 st.insert(0); // 考虑到左右两边各有一个相同mass的情况,这时称不了物体! 13 st.insert(a); // 只选一个mass称物体 14 st.insert(b); 15 st.insert(c); 16 17 st.insert(a+b); // 只选两个mass称另外一边的物体 18 st.insert(abs(a-b)); 19 st.insert(b+c); 20 st.insert(abs(b-c)); 21 st.insert(a+c); 22 st.insert(abs(a-c)); 23 24 st.insert(abs(a+b-c)); // 两个mass在一边,另一边放第三个mass和代称物 25 st.insert(abs(a+c-b)); 26 st.insert(abs(b+c-a)); 27 28 st.insert(a+b+c); // 三个mass在一边,另一边称物体 29 return st.size()-1; 30 } 31 32 int main() 33 { 34 int T, x, y, sum; 35 while (scanf("%d", &T) != EOF) 36 { 37 while (T--) 38 { 39 sum = 0; 40 scanf("%d%d", &x, &y); 41 for (int i = 1; i <= x; i++) 42 { 43 int t1 = i; 44 int t2 = x-i; 45 int t3 = y; 46 sum = max(sum, cal(t1, t2, t3)); 47 } 48 for (int i = 1; i <= y; i++) 49 { 50 int t1 = i; 51 int t2 = y-i; 52 int t3 = x; 53 sum = max(sum, cal(t1, t2, t3)); 54 } 55 printf("%d\n", sum); 56 } 57 } 58 return 0; 59 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。