美团笔试 2022.3.19
只ac了前两道，后两道有corner case没考虑到。大家交流一下，顺便求正确做法！！！
------------------------------------------------------------------------------------------------------------------
第三题已更正，我确信是对的
第四题已更正，参照一位dalao做法 https://www.nowcoder.com/discuss/868013?type=2
第一题
import java.util.Scanner;
public class Solution1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int productNum = sc.nextInt();
int[][] product = new int[productNum][2];
for (int i = 0; i < productNum; i++) {
product[i][0] = sc.nextInt();
}
for (int i = 0; i < productNum; i++) {
product[i][1] = sc.nextInt();
}
int princpleNum = sc.nextInt();
int[][] princple = new int[princpleNum][2];
for (int i = 0; i < princpleNum; i++) {
princple[i][0] = sc.nextInt();
}
for (int i = 0; i < princpleNum; i++) {
princple[i][1] = sc.nextInt();
}
System.out.println(getOutPut(productNum, product, princpleNum, princple));
}
private static String getOutPut(int productNum, int[][] product, int princpleNum, int[][] princple) {
StringBuilder res = new StringBuilder();
int productRawPrice = 0;
int productMinusPrice = 0;
int princplePtr = -1;
for (int ptr = 0; ptr < productNum; ptr++) {
productRawPrice += product[ptr][0];
productMinusPrice += product[ptr][1];
int tmpPrice = productRawPrice;
while (princplePtr + 1 < princpleNum && productRawPrice >= princple[princplePtr + 1][0]) {
princplePtr++;
}
if (princplePtr > -1) {
tmpPrice -= princple[princplePtr][1];
}
if (tmpPrice > productMinusPrice) {
res.append('Z');
} else if (tmpPrice < productMinusPrice) {
res.append('M');
} else {
res.append('B');
}
}
return res.toString();
}
} import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Solution2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int strLen = sc.nextInt();
int operation = sc.nextInt();
sc.nextLine();
String str = sc.nextLine();
System.out.println(operateStr(str, operation));
}
private static String operateStr(String str, int operation) {
if (operation == 1) {
return encodeStr(str);
} else {
return decodeStr(str);
}
}
private static String decodeStr(String str) {
List<Character> output = new ArrayList<>();
char[] ch = str.toCharArray();
int strLen = str.length();
for (int i = strLen - 1; i > -1; i--) {
int index = (output.size() + 1 + 1) / 2 - 1;
output.add(index, ch[i]);
}
StringBuilder sb = new StringBuilder();
for (char tmpChar : output) {
sb.append(tmpChar);
}
return sb.toString();
}
private static String encodeStr(String str) {
int strLen = str.length();
List<Character> input = new ArrayList<>();
for (int i = 0; i < strLen; i++) {
input.add(str.charAt(i));
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < strLen; i++) {
int tmpLen = input.size();
int index = (tmpLen + 1) / 2 - 1;
sb.append(input.remove(index));
}
return sb.toString();
}
} import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Solution3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long fileNum = sc.nextLong();
int changedFileNumOnBook = sc.nextInt();
int changedFileNumOnCom = sc.nextInt();
long[][] bookChange = new long[changedFileNumOnBook][2];
long[][] comChange = new long[changedFileNumOnCom][2];
for (int i = 0; i < changedFileNumOnBook; i++) {
bookChange[i][0] = sc.nextLong();
}
for (int i = 0; i < changedFileNumOnBook; i++) {
bookChange[i][1] = sc.nextLong();
}
for (int i = 0; i < changedFileNumOnCom; i++) {
comChange[i][0] = sc.nextLong();
}
for (int i = 0; i < changedFileNumOnCom; i++) {
comChange[i][1] = sc.nextLong();
}
System.out.println(getConflictFileNum(changedFileNumOnBook, changedFileNumOnCom, bookChange, comChange));
}
private static int getConflictFileNum(int changedFileNumOnBook, int changedFileNumOnCom, long[][] bookChange, long[][] comChange) {
Arrays.sort(bookChange, (o1, o2) -> {return (int) (o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);});
Arrays.sort(comChange, (o1, o2) -> {return (int) (o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);});
bookChange = merge(bookChange);
comChange = merge(comChange);
changedFileNumOnBook = bookChange.length;
changedFileNumOnCom = comChange.length;
int res = 0;
int bookPtr = 0;
int comPtr = 0;
while (bookPtr < changedFileNumOnBook && comPtr < changedFileNumOnCom) {
long[] book = bookChange[bookPtr];
long[] com = comChange[comPtr];
if (book[1] > com[1]) {
if (book[0] <= com[0]) {
res += com[1] - com[0] + 1;
} else if (book[0] <= com[1]) {
res += com[1] - book[0] + 1;
}
comPtr++;
} else {
if (com[0] <= book[0]) {
res += book[1] - book[0] + 1;
} else if (com[0] <= book[1]) {
res += book[1] - com[0] + 1;
}
bookPtr++;
}
}
return res;
}
private static long[][] merge(long[][] change) {
List<long[]> ls = new ArrayList<>();
int len = change.length;
if (len == 0) {
return change;
}
ls.add(change[0]);
for (int i = 1; i < len; i++) {
long[] tmp = change[i];
long[] pre = ls.get(ls.size() - 1);
if (tmp[0] > pre[1]) {
ls.add(tmp);
} else {
pre[1] = Math.max(tmp[1], pre[1]);
}
}
return ls.toArray(new long[0][0]);
}
}
第四题
import java.util.Arrays;
import java.util.Scanner;
public class Solution4 {
private static long maxValue = 0;
private static int possNum = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int ballNum = sc.nextInt();
int k1 = sc.nextInt();
int k2 = sc.nextInt();
int[] ball = new int[ballNum];
for (int i = 0; i < ballNum; i++) {
ball[i] = sc.nextInt();
}
computeCombination(ball, k1, k2);
System.out.print(maxValue + " " + possNum);
}
private static void computeCombination(int[] ball, int k1, int k2) {
int divisor = (k1 * k2) / maxCommonDivisor(k1, k2);
int len = ball.length;
//从前i个数中选取一个组合，组合的数字和为n，n必须满足余divisor为j。valueDp[i][j]记录了最大的n，timesDp[i][j]记录了n为valueDp[i][j]的组合数
//为什么要余divisor？已知preNum，newNum是使得preNum % k1 == num % k1 && preNum % k2 == num % k2成立的num的最小值，那么：preNum % divisor == newNum
int[][] valueDp = new int[len + 1][divisor];
int[][] timesDp = new int[len + 1][divisor];
for (int i = 0; i <= len; i++) {
for (int j = 0; j < divisor; j++) {
//必须初始化为极小的数
valueDp[i][j] = -0x3f3f3f3f;
}
}
valueDp[0][0] = 0;
timesDp[0][0] = 1;
for (int i = 1; i <= len; i++) {
for (int j = 0; j < divisor; j++) {
valueDp[i][j] = Math.max(valueDp[i][j], valueDp[i - 1][j]);
//确保余数为正数
int index = ((j + ball[i - 1]) % divisor + divisor) % divisor;
if (valueDp[i - 1][j] != -0x3f3f3f3f) {
valueDp[i][index] = Math.max(valueDp[i][index], valueDp[i - 1][j] + ball[i - 1]);
}
}
for (int j = 0; j < divisor; j++) {
if (valueDp[i][j] == valueDp[i - 1][j]) {
timesDp[i][j] = (timesDp[i][j] + timesDp[i - 1][j]) % 998244353;
}
int index = ((j + ball[i - 1]) % divisor + divisor) % divisor;
if (valueDp[i][index] == valueDp[i - 1][j] + ball[i - 1]) {
timesDp[i][index] = (timesDp[i][index] + timesDp[i - 1][j]) % 998244353;
}
}
}
for (int j = 0; j < divisor; j++) {
if (j % k1 == 0 && j % k2 != 0) {
if (valueDp[len][j] > maxValue) {
maxValue = valueDp[len][j];
possNum = timesDp[len][j];
}
}
}
}
//求最大公约数
public static int maxCommonDivisor(int m, int n) {
if (m < n) { //保证被除数大于除数
int temp = m;
m = n;
n = temp;
}
while (m % n != 0) { //在余数不能为0时,进行循环
int temp = m % n;
m = n;
n = temp;
}
return n; // 返回最大公约数
}
}
