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
西月弦 閱讀(301)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告