牛客编程巅峰赛S1第8场 - 黄金&钻石
A 牛牛的分配
解题思路
这道题贪心的来想，如果想让尽可能多的瓶子满足要求，则应该让所有瓶子的初始容量尽可能的大，所以做法就是我们对所有的瓶子按照初始的容量从小到大排序，然后从后往前看，累加所有瓶子的容积，然后除以它们的个数，直到当前所有瓶子的容积的平均值小于,就跳出循环。
参考代码
import java.util.*;
public class Solution {
/**
* 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量
* @param n int整型 瓶子的数量
* @param x int整型 牛牛的对瓶中的水量要求
* @param a int整型一维数组 每个瓶子中的含水量
* @return int整型
*/
public int solve (int n, int x, int[] a) {
// write code here
Arrays.sort(a, 0, n);
// 如果当前容量最多的瓶子的容积都小于x，则该序列绝对不满足要求
if(a[n - 1] < x) return 0;
long sum = 0;
int res = 1;
for(int i=n-1; i>=0; i--){
sum += a[i];
int cur = n - 1 - i + 1; // 获得当前的瓶子个数
if(sum >= (long)x * cur){ // 以防出现精度问题
res = Math.max(res, cur);
}else break;
}
return res;
}
}B playfair
解题思路
这道题就是一个模拟题，按照题目的意思来就行，需要注意的是加密过程中的j都由i来代替, 在替换明文的时候需要注意
参考代码
import java.util.*;
public class Solution {
/**
* playfair加密算法
* @param key string字符串 密钥
* @param str string字符串 明文
* @return string字符串
*/
public String Encode (String key, String str) {
// write code here
char[][] g = new char[5][5]; // 设计密码表
List<Character> s = new ArrayList<Character>();
for(int i=0; i<key.length(); i++) {
char c = key.charAt(i);
if(s.contains(c)) continue;
if(c == 'j') c = 'i';
if(!s.contains(c)) s.add(c);
}
// 先将已有的字符填入密码表
int x = 0;
int y = 0;
for(Character c : s) {
g[x][y ++] = c;
if(y == 5) {
x += 1;
y = 0;
}
}
// 补全没有的字符
while(x != 5 || y != 0) {
for(char c ='a'; c<='z'; c++) {
if(!s.contains(c) && c != 'j') {
g[x][y] = c;
s.add(g[x][y]);
break;
}
}
y ++;
if(y == 5) {
x += 1;
y = 0;
}
}
// 使用StringBuilder使得字符串拼接效率更高
StringBuilder res = new StringBuilder();
for(int i=0; i<str.length(); i+=2) {
// 截取字符串str
String cur = str.substring(i, Math.min(i+2, str.length()));
if(cur.length() < 2) {
res.append(cur);
}else {
char a = cur.charAt(0);
char b = cur.charAt(1);
// 如果明文中含有j，则将其替换为i
if(a == 'j') a = 'i';
if(b == 'j') b = 'i';
// 获取a和b两个字符在矩阵中的位置
int x1 = -1; int y1 = -1;
int x2 = -1; int y2 = -1;
for(int u=0; u<5; u++) {
for(int v=0; v<5; v++) {
if(g[u][v] == a) {
x1 = u;
y1 = v;
}
if(g[u][v] == b) {
x2 = u;
y2 = v;
}
}
}
if(x1 == x2 && y2 == y1){
String c = a + "";
res.append(c + c);
}else if(x1 == x2) {
String c = g[x1][(y1+1)%5] + "";
String d = g[x2][(y2+1)%5] + "";
res.append(c + d);
}else if(y1 == y2) {
String c = g[(x1+1)%5][y1] + "";
String d = g[(x2+1)%5][y2] + "";
res.append(c + d + "");
}else if(x1 != x2 && y1 != y2){
String c = g[x1][y2] + "";
String d = g[x2][y1] + "";
res.append(c + d + "");
}
}
}
return res.toString();
}
}C 牛牛摇骰子
解题思路
首先这道题贪心的来想，对于所有大于11的数字，当然优先用11来将它们变得更小，但是这里要考虑一个特殊的数字，也算是打表找出的规律吧，就是例如13，它实际上只需要3步，也就是0 - > 3 - > 10 - > 13, 对于24，
0 - > 7 - > 14 > 21 - > 24，只需要4步，但是如果按照贪心的想法来做的话，对于13就需要5步，对于24就需要6步，故我们可以发现，所有模11余2的数字都比按贪心直接做的要少2步，而对于剩下的数字都是可以正确计算的，因此最终我的做法就是预先处理出来[0, 22]的所有数字需要的最小步数，然后对于每一个新的数字，优先让它们被11削减，然后与剩下数字所需的最小步数相加就ok了。
参考代码
import java.util.*;
public class Solution {
/**
* 把所有询问的答案按询问顺序放入vector里
* @param arr int整型一维数组 要查询坐标的数组
* @return int整型一维数组
*/
public int[] MinimumTimes (int[] arr) {
// write code here
// BFS出22以内的数字的最小步数使用(0, 3, 7, 11)来构造
int[] a = {0, 3, 7, 11};
int[] d = new int[23];
boolean[] st = new boolean[23];
Queue<Integer> q = new LinkedList<Integer>();
q.add(0);
d[0] = 0;
st[0] = true;
while(!q.isEmpty()){
int cur = q.poll();
for(int i=0; i<a.length; i++){
int u = cur + a[i];
int v = cur - a[i];
if((u <= 22 && u >= 0) && !st[u]){
st[u] = true;
d[u] = d[cur] + 1;
q.add(u);
}
if((v <= 22 && v >= 0) && !st[v]){
st[v] = true;
d[v] = d[cur] + 1;
q.add(v);
}
}
}
int[] res = new int[arr.length];
for(int i=0; i<arr.length; i++) {
int cur = arr[i];
if(cur <= 11) {
res[i] = d[cur % 11];
}else {
int u = cur / 11 - 1;
int v = d[cur % 11 + 11];
res[i] = u + v;
}
}
return res;
}
}
Momenta公司福利 281人发布