搜狐2016筆試題

第一題 馬拉松分獎金

• N組人進行馬拉松賽，賽後有獎金
• 獎金機關1w，每組至少1w
• 每組可以知道相鄰組的成績
• 如果比相鄰組成績高，則獎金也要高于相鄰組
• 問最少要多少獎金
• 輸入N行資料，表示N個組的成績。輸出獎金值

我的AC答案，算法不高端，隻簡單寫起來快

#include <iostream>
#include <vector>
using namespace std;
int panduan(vector<int>& v,vector<int>& p) {
    int len = v.size();
    bool flag = ;
    while (flag) {
        flag = ;
        for (int i = ; i < len; i++) {
            int l = i - , r = i + ;
            if (l >= ) {
                if (v[i] > v[l] && p[i] <= p[l]) {
                    p[i] = p[l] + ;
                    flag = ;
                }
            }
            if (r < len) {
                if (v[i] > v[r] && p[i] <= p[r]) {
                    p[i] = p[r] + ;
                    flag = ;
                }
            }
        }
    }
    int sum = ;
    for (int i = ; i < len; i++) {
        sum += p[i];
    }
    return sum;

}

int main()
{
    int t;
    vector<int> v;
    while (cin>>t) {
        v.push_back(t);
    }
    vector<int> p(v.size(), );
    cout << panduan(v, p) << endl;
    return ;
}
           

第二題 馬戲團疊羅漢

• 馬戲團有一組人，希望表演疊羅漢
• 要求下面的人不比上面的人輕、矮，同時滿足
• 問最多疊幾層

• 輸入 N，表示n個人；接下來為每個人的id、體重、身高。

  輸出最多疊的人數。

我的解法暴力搜尋，隻有60%正确率，求大神的正解

#include <iostream>
#include <vector>
using namespace std;
int dfs(const vector<int>& w, const vector<int>& h, int topw,int toph,vector<bool>& isset,const int len) {
    //cout << topw << ' ' << toph << endl;
    int r = ,t;
    for (int i = ; i < len; i++) {
        if (!isset[i]) {
            if (toph == - ) {
                isset[i] = ;
                t = dfs(w, h, w[i], h[i], isset, len) + ;
                isset[i] = ;
                if (t > r) r = t;

            }
            else {
                if (w[i] <= topw && h[i] <= toph) {
                    isset[i] = ;
                    t = dfs(w, h, w[i], h[i], isset, len) + ;
                    isset[i] = ;
                    if (t > r) r = t;

                }
            }
        }
    }
    //cout << r << endl;
    return r;
}
int main()
{
    int n;
    cin >> n;
    vector<int> weight(n,);
    vector<int> height(n,);
    vector<bool> isset(n,false);
    for (int i = ; i < n; i++) {
        int id, w, h;
        cin >> id >> w >> h;
        weight[i] = w;
        height[i] = h;
    }
    cout<<dfs(weight, height,-,-, isset,n)<<endl;
    return ;
}
           

第三題 炸金花

• 兩個人玩紮金花
• 豹子最大，再是順子，再是對子。不能A23
• 同樣種類的牌就比大小
• 牌用“2345678910JQK”表示
• 輸入為兩個字元串，例如“QKA” “457”，沒有大小王。
• 甲赢輸出1，乙赢輸出-1，平局輸出0，輸入不對輸出-2

沒時間做，應該隻要處理一下，排個序，判斷種類完了比大小就行了。