搜狐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

没时间做，应该只要处理一下，排个序，判断种类完了比大小就行了。