去哪儿笔试

第一题：因为硬币面值1，5，10，50，100，500相邻面值之间为后者为前者的倍数，因此，可以直接贪心的做。
AC代码：

#include <iostream>
#include <algorithm>

//#include <fstream>

using namespace std;

int main(){
    //ifstream cin("input.txt");

    int c1, c5, c10, c50, c100, c500, a;
    int res, cnt;
    while(cin>>c1>>c5>>c10>>c50>>c100>>c500>>a)
    {
        res = 0;
        if(c500 > 0 && a >= 500)
        {
            cnt = a / 500;
            if(cnt > c500) cnt = c500;
            c500 -= cnt;
            res += cnt;
            a -= cnt *500;
        }
        if(c100 > 0 && a >= 100)
        {
            cnt = a / 100;
            if(cnt > c100) cnt = c100;
            c100 -= cnt;
            res += cnt;
            a -= cnt *100;
        }
        if(c50 > 0 && a >= 50)
        {
            cnt = a / 50;
            if(cnt > c50) cnt = c50;
            c50 -= cnt;
            res += cnt;
            a -= cnt *50;
        }
        if(c10 > 0 && a >= 10)
        {
            cnt = a / 10;
            if(cnt > c10) cnt = c10;
            c10 -= cnt;
            res += cnt;
            a -= cnt *10;
        }
        if(c5 > 0 && a >= 5)
        {
            cnt = a / 5;
            if(cnt > c5) cnt = c5;
            c5 -= cnt;
            res += cnt;
            a -= cnt *5;
        }
        if(c1 > 0 && a >= 1)
        {
            cnt = a;
            if(cnt > c1) cnt = c1;
            c1 -= cnt;
            res += cnt;
            a -= cnt;
        }
        if(a != 0) cout<<"NOWAY"<<endl;
        else cout<<res<<endl;
    }

    return 0;
}

第二题：在普通拓扑排序的基础上加了一个限制条件，注意每次选入读为0的点中权重最大的，需要注意权重相同时的情况。
AC代码：

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <unordered_map>

//#include <fstream>

using namespace std;

const int maxn = 10005;

int weight[maxn];
int inDegree[maxn];
set<int> g[maxn];
unordered_map<int, int> idx;
unordered_map<int, int> idx_r;
int n, e, seq, w, s, t;
vector<int> res;

struct cmp
{
    bool operator()(const int &a, const int &b)const
    {
        if(weight[a] != weight[b]) return weight[a] > weight[b];
        int maxa = 0, maxb = 0;
        for(auto it = g[a].begin(); it != g[a].end(); it++)
        {
            if(inDegree[*it] == 1 && weight[*it] > maxa) maxa = weight[*it];
        }
        for(auto it = g[b].begin(); it != g[b].end(); it++)
        {
            if(inDegree[*it] == 1 && weight[*it] > maxb) maxb = weight[*it];
        }
        if(maxa != maxb) return maxa > maxb;
        return a < b;
    }
};

set<int, cmp> st;

void init()
{
    memset(inDegree, 0, sizeof(int) * (n + 1));
    for(int i = 1; i <= n; ++i) g[i].clear();
    idx.clear();
    idx_r.clear();
    st.clear();
    res.clear();
}

int main(){
    //ifstream cin("input.txt");

    while(cin>>n>>e)
    {
        init();
        for(int i = 1; i <= n; ++i)
        {
            cin>>seq>>w;
            idx[seq] = i;
            idx_r[i] = seq;
            weight[idx[seq]] = w;
        }
        while(e--)
        {
            cin>>s>>t;
            if(g[idx[s]].find(idx[t]) == g[idx[s]].end())
            {
                g[idx[s]].insert(idx[t]);
                ++inDegree[idx[t]];
            }
        }
        for(int i = 1; i <= n; ++i)
        {
            if(inDegree[i] == 0) st.insert(i);
        }
        while(!st.empty())
        {
            auto it = st.begin();
            int x = *it;
            st.erase(it);
            res.push_back(x);
            for(auto it1 = g[x].begin(); it1 != g[x].end(); it1++)
            {
                int y = *it1;
                if(--inDegree[y] == 0)
                {
                    st.insert(y);
                }
            }
        }

        for(int i = 0; i < n - 1; ++i) cout<<idx_r[res[i]]<<" ";
        cout<<idx_r[res[n - 1]]<<endl;
    }

    return 0;
}

第三题：LRU，禁用hash表，可采用map（红黑树）来记录键值对。这里有一个trick，就是用一个计数以及一个队列，实现了每次put或者get操作的复杂度为O(logn)（因为采用的红黑树，若采用hash表，则为O(1)）。
AC代码：

#include <iostream>
#include <map>
#include <string>
#include <queue>

//#include <fstream>

using namespace std;

map<string, string> mp_kv;
map<string, int> mp_cnt;
queue<string> q;
int m, n;

void init()
{
    mp_kv.clear();
    mp_cnt.clear();
    while(!q.empty()) q.pop();
}

void put(string &k, string &v)
{
    mp_kv[k] = v;
    ++mp_cnt[k];
    q.push(k);
    if(mp_kv.size() > m)
    {
        while(!q.empty())
        {
            string s = q.front();
            q.pop();
            if(--mp_cnt[s] == 0)
            {
                mp_kv.erase(s);
                break;
            }
        }
    }
}

bool get(string &k, string &res)
{
    if(mp_kv.find(k) != mp_kv.end())
    {
        res = mp_kv[k];
        ++mp_cnt[k];
        q.push(k);
        return true;
    }
    return false;
}

int main(){
    //ifstream cin("input.txt");

    string op, k, v;
    while(cin>>m>>n)
    {
        init();
        while(n--)
        {
            cin>>op;
            if(op[0] == 'p')
            {
                cin>>k>>v;
                put(k, v);
            }
            else
            {
                cin>>k;
                if(get(k, v)) cout<<v<<endl;
                else cout<<"null"<<endl;
            }
        }
    }

    return 0;
}