250pt
有高度为a的木棍ca个, 高度为b的木棍cb个, 两种不同的木棍只允许交叉摆放, 问可以组成的不同长度.
算法分析:
只能是abababa或者bababab这种, 总的来说有三种情况, a和b的数量相等, 或者a多一个, 或者b多一个, 考虑a和b是否相等或者ca和cb是否相等.
代码:
srm554-250pt
1 class
2 TheBrickTowerEasyDivOne{
3 int min(int a,int b){if(a<b) return a;return b;}
4 public : int find(int rc,int a,int bc,int b){
5 int t = min(rc,bc);
6 int ans = t+2;
7 if(a == b) ans += t;
8 else ans += 2*t;
9 ans --;
10 if(bc == rc) ans --;
11 return ans;
12 }
13 500pt
给一个序列a,每个元素都有一个值, 现在让你重新排列这个序列, 让每两个相邻元素的最大值总和最小, 如果有多个选择则保证字典序最小.
算法分析:
最小的情况有一种就是每个元素, 除了最小的都只取一次. 然后不断把字典序小的元素放在前面看是否会影响结果.
代码:
srm554-500pt
1 #include<algorithm>
2 #include<iostream>
3 #include<vector>
4 using namespace std;
5 class
6 TheBrickTowerMediumDivOne{
7 public : vector <int> find(vector <int> h){
8 vector<pair<int,int> > num;
9 vector<int> ans;
10 ans.push_back(0);
11 int s, n = h.size();
12 int vis[100] = {0};
13 vis[0] = 1;
14 for(s = 1; s < n; s ++) {
15 int k = -1;
16 for(int t = 0; t < n; t++)
17 if(!vis[t] && h[t] <= h[ans[s-1]]){k = t; break;}
18 if(k == -1) break;
19 else vis[k] = 1;
20 ans.push_back(k);
21 }
22 for(int i = 0; i < n; i++) if(!vis[i]) num.push_back(make_pair(h[i],i));
23 sort(num.begin(),num.end());
24 for(int i = 0; i < num.size(); i++) ans.push_back(num[i].second);
25 return ans;
26 }
27
posted on 2012-09-02 09:28
西月弦 阅读(285)
评论(0) 编辑 收藏 引用 所属分类:
解题报告