A-牛牛的分配

在牛牛面前有n个瓶子，每个瓶子的大小体积都一样，但是每个瓶子内的含水量都不相同。
因为牛牛是个完美主义者，他希望瓶子中的水能够满足他的要求，他的要求是瓶子中的水最少为x。所以他打算对这些瓶子里的水进行重新分配，以满足最多的瓶子中水量大于等于x。
牛牛的分配规则是：每次可以选择多个瓶子，将里面的水平均分配到已选择的瓶子中。
给定n个瓶子和牛牛的对瓶中的水量要求x，以及n个瓶子中的含水量，求最多可以有多少个瓶子满足牛牛的要求？

分析

将水量从小到大排序，对于含水量超过x的瓶子，它可以对答案做出贡献，对于含水量没到x的瓶子，我们希望它与x的差值越小越好，所以可以先排序，从前往后利用前缀和计算水量和是否满足条件，更新答案。

typedef long long LL;
class Solution {
public:
    /**
     * 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量
     * @param n int整型 瓶子的数量
     * @param x int整型 牛牛的对瓶中的水量要求
     * @param a int整型vector 每个瓶子中的含水量
     * @return int整型
     */
    int solve(int n, int x, vector<int>& a) {
        sort(a.begin(),a.end());
         
        vector<LL> s(n+1,0);   //会爆int
         
        for(int i = 1; i<=n; i++) s[i]  = s[i-1] + a[i-1];
         
        int ans = 0;
         
        for(int i = 1; i<=n; i++){
            if(s[n]- s[i-1] >= (n-i+1)*x) ans = max(ans,n-i+1);
        }
        return ans;
    }
};

B - playfair

problem

分析

按照题意模拟即可，注意细节，以及一遇到j，我们必须换成i。

typedef pair<int,int> PII;
class Solution {
public:
    /**
     * playfair加密算法
     * @param key string字符串 密钥
     * @param str string字符串 明文
     * @return string字符串
     */
    string Encode(string key, string str) {
        int n = key.size();
        int cnt = 0;
        map<char,bool> h;
        map<char,PII> st;
        vector<vector<char>> c(6,vector<char>(6,0));
        for(int i = 0; i<5; i++){
            for(int j = 0; j<5; j++){
                if(cnt == n){
                    for(int k = 0; k<26; k++){
                        char ch = 'a'+k;
                        if(ch == 'j') ch = 'i';
                        if(h[ch]) continue;
                        c[i][j] = ch;
                        st[ch] = make_pair(i,j);
                        h[ch] = true;
                        break;
                    }
                    continue;
                }
                if(key[cnt] == 'j') key[cnt] = 'i';
                while(h[key[cnt]] && cnt <n) {
                    cnt ++;
                    if(key[cnt] == 'j') key[cnt] = 'i';
                }
                if(cnt == n) {
                    for(int k = 0; k<26; k++){
                        char ch = 'a'+k;
                        if(ch == 'j') ch = 'i';
                        if(h[ch]) continue;
                        c[i][j] = ch;
                        st[ch] = make_pair(i,j);
                        h[ch] = true;
                        break;
                    }
                    continue;
                }
                h[key[cnt]] = true;
                st[key[cnt]] = make_pair(i,j);
                c[i][j] = key[cnt++];
            }
        }
        
        string ans = "";
        int m = str.size();
        char a,b;
        int x,y;
        for(int i = 0; i<m; i += 2){
            a = str[i];
            if(i+1==m){
                ans += a;
                break;
            }else
                b = str[i+1];
            if(a == 'j') a = 'i';
            if(b == 'j') b = 'i';
            if(a == b) ans = ans + a + a;
            else if(st[a].first == st[b].first){
                x = st[a].first;
                y = st[a].second;
                ans = ans + c[x][(y+1)%5];
                y = st[b].second;
                ans = ans + c[x][(y+1)%5];
            }else if(st[a].second == st[b].second){
                y = st[a].second;
                x = st[a].first;
                ans = ans + c[(x+1)%5][y];
                x = st[b].first;
                ans = ans + c[(x+1)%5][y];
            }else{
                x = st[a].first;
                y = st[a].second;
                int u = st[b].first;
                int v = st[b].second;
                ans = ans + c[x][v];
                ans = ans + c[u][y];
            }
        }
        return ans;
    }
};

C - 牛牛摇骰子

牛牛非常擅长摇骰子，不管给他一个什么样的骰子他都能准确的掷出他想要的那一面。现在有一个四面体骰子，四个面分别是四个整数0,3,7,11。牛牛在玩一个游戏。牛牛初始在一个数轴的原点，每当他摇出一个数字x，他可以自行选择向左走x步或者向右走x步。牛牛想知道他最少摇多少次骰子可以从原点到达坐标为p的点。
现在一共有N次询问，请你返回从0点到询问的每一个坐标arr[i]所需要摇筛子的最小次数。

分析

显然，对于距离很大的点，我们肯定是先用11走到距离0很近的点，那么我们可以先预处理出11范围内各点所需摇骰子的最小次数，然后先用11走，再用小的点走，有一个特殊情况，就是如果x为2，那么需要走4步，如果x为13，不需要走5步，走3步即可，（0->3->3->7）,前面的最小步数可以通过bfs算出。

typedef long long LL;
class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
    vector<int> MinimumTimes(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans;
        
        vector<int> pre = {0,3,2,1,2,3,2,1,2,3,2};

        for(int i = 0; i<n; i++){
            
            int t = arr[i];
            if(t==2) {
                ans.push_back(4);
                continue;
            }
            ans.push_back(pre[t%11]+t/11);
            
        }
        return ans;
    }
};