8.26-美团-笔试
只做出了三道半。。。感觉美团换成牛客平台后，特别针对Java选手，同样的思路cpp、py都能过。。。
第一题：小美种果树
当时直接模拟就好了，我在这边找规律，做了快半个小时
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
int yu = z%(3*x+y); //一个周期三天 成长值3*x+y ,
int ans =0;
if(yu==0) {
ans = 3* (z/(3*x+y));
}else {
if(yu<x+y){
ans = 3* (z/(3*x+y))+1;
}
else if(yu<2*x+y){
ans = 3* (z/(3*x+y))+2;
}else {
ans = 3* (z/(3*x+y))+3;
}
}
System.out.println(ans);
}
第二题：小美结账
直接模拟
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long a[] = new long[m + 2];
for (int i = 1; i <= n; i++){
int k = sc.nextInt();
int c = sc.nextInt();
int avg = (c+k-1)/k;//向上取整
for (int j = 1; j <= k-1; j++){
int id = sc.nextInt();
a[id] += avg;
}
}
for (int i = 1; i <= m; i++){
if(i==1){
System.out.print(a[i]);
}else {
System.out.print(" ");
System.out.print(a[i]);
}
}
System.out.println("");
}
第三题：小美的游戏
小美有一个长度为n的数组，她最多可以进行k次操作，每次操作如下：
- 选择两个整数i,j(1<=i<j<=n)
- 选择两个整数x,y，使得x*y=ai*aj
- 将ai替换为x，将aj替换为y
她希望最多进行k次操作之后，最后数组中的元素的总和尽可能大。
思路：堆模拟。找到堆中最大的两个元素相乘，再往堆里加入相乘的值和1，循环k次即可。
static final int MOD = (int) 1e9 + 7;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
PriorityQueue<BigDecimal> pq = new PriorityQueue<>((a, b) -> b.compareTo(a));
for (int i = 0; i < n; i++) {
long x = sc.nextInt();
pq.offer(BigDecimal.valueOf(x));
}
BigDecimal ans = BigDecimal.valueOf(0);
while (k-- > 0) {
BigDecimal x = pq.poll(), y = pq.poll();
pq.offer(x.multiply(y));
pq.offer(BigDecimal.valueOf(1));
}
while (!pq.isEmpty()) {
ans = ans.add(pq.poll());
}
System.out.println(ans.divideAndRemainder(BigDecimal.valueOf(MOD))[1]);
}
第四题：小美的数组重排
小美有两个长度为n的数组a和b。
小美想知道，能不能通过重排a数组使得对于任意1<=i<=n,1<=ai+bi<=m？
将会有q次询问。
思路：要想满足题目的要求，对于数组a的最小值，如果跟数组b的最大值进行合并，假设结果不满足，那就肯定是不可能的了，否则可以考虑次小值和次大值进行分配，以此类推，只需要将a数组正向排序，b数组逆向排序即可。
static final int N = 510;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
while (q-- > 0) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
b[i] = sc.nextInt();
}
Arrays.sort(a);
Arrays.sort(b);
boolean flag = true;
for (int i = 0, j = n - 1; i < n; i++, j--) {
if (!(a[i] + b[j] >= 1 && a[i] + b[j] <= m)) {
flag = false;
break;
}
}
System.out.println(flag ? "YES" : "NO");
}
}
第五题：平均数为k的最长连续子数组
给定n个正整数组成的数组，求平均数正好等于k 的最长连续子数组的长度。
如果不存在任何一个连续子数组的平均数等于k，则输出-1。
否则输出平均数正好等于k的最长连续子数组的长度。
思路：思维题+哈希表模拟。
平均数比较难处理，我们不妨将原数组中每个元素都-k，这样问题转换成找到和为0的最长子数组。
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt() - k;
}
int res = 0;
HashMap<Integer, Integer> occ = new HashMap<>();
occ.put(0, -1);
int tmp = 0;
for (int i = 0; i < n; i++) {
tmp += a[i];
if (occ.containsKey(tmp)) {
res = Math.max(res, i - occ.get(tmp));
}
if (!occ.containsKey(tmp)) {
occ.put(tmp, i);
}
}
System.out.println(res);
}
