题目链接：戳这里
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;
}
};
