2023年美团秋招编程岗第二批笔试

class main1 { public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); //输入数组元素 String[]s=br.readLine().split(" "); long[]a=new long[n]; for(int i=0;i<n;i++){ a[i]=Long.parseLong(s[i]); } //cur记录当前元素和上一个元素相乘的最大值，若改变，则记录当前元素的下标curId BigInteger max=BigInteger.valueOf(-1); BigInteger sum=BigInteger.valueOf(0); int curId=0; for(int i=1;i<n;i++){ BigInteger curVal=BigInteger.valueOf(a[i]); BigInteger lastVal=BigInteger.valueOf(a[i-1]); BigInteger cur=curVal.multiply(lastVal); if(cur.compareTo(max)>0){ curId=i; max=cur; } sum=sum.add(curVal); } BigInteger ans=sum.add(max) .add(BigInteger.valueOf(a[0])) .subtract(BigInteger.valueOf(a[curId])) .subtract(BigInteger.valueOf(a[curId-1])); System.out.println(ans); } }

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.reflect.Array; import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { //输入 Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[]a=new int[n]; long sum=0; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); sum+=a[i]; } //众数的最大可能出现次数是n/n-1 //n--sum%n==0，所有元素全部相同 //n-1--sum%n!=0，需要舍弃一个元素,剩下n-1个元素全部相同 long ans=0L; if(sum%n==0){ //n个元素相同，众数出现次数为n long target=sum/n; ans=calOps(a,target,-1); }else{ //n-1个元素相同，众数出现次数为n-1 Arrays.sort(a); //比较排除最大值/最小值后，哪种情况得到的操作数更小 ans=Math.min(cal(a,sum,0), cal(a,sum,a.length-1)); } System.out.println(ans); } //排除一个元素后，计算最小操作数 private static long cal(int[] a, long sum, int exId) { sum=sum-a[exId]; long target=sum/(a.length-1); if(sum%(a.length-1)==0){ //能整除 return calOps(a,target,exId); }else{ //不能整数，target上下分别取整计算一次 return Math.min(calOps(a,target,exId),calOps(a,target+1,exId)); } } //计算 把元素变成target的操作数 private static long calOps(int[] a, long target, int exId) { long add=0L; long minus=0L; for(int i=0;i<a.length;i++){ if(i==exId)continue;//跳过被排除的元素 if(target-a[i]>0){ add+=target-a[i];//累加需要增加的次数 }else{ minus+=a[i]-target;//累计需要减少的次数 } } //每次操作可以同时处理一次add和minus，抵消后剩下的差由被排除的元素承担 return Math.max(add,minus); } }

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; //相邻字符都不相等的01串只有两种可能 //0开头，01交替 //1开头，10交替 public class Main { static boolean isAchieved; public static void main(String[] args) { Scanner sc=new Scanner(System.in); char[]s=sc.next().toCharArray(); int n=s.length; int[][][]dp=new int[n][n][2]; int res=0; //dp[i][j][k]子串i~j变成结尾为k的交替串，需要反转的次数 dp[0][0][s[0]-'0']=0;//结尾是原字符，翻转次数0 dp[0][0][1-s[0]+'0']=1;//结尾是翻转后的字符，翻转次数1 for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ if(i==0&&j==0)continue;//已完成初始化，跳过 int bit=s[j]-'0';//当前字符原始值 //以当前字符结尾，翻转次数等于【i,j-1】结尾为1-bit（和当前位不同）的次数 dp[i][j][bit]=dp[i][j-1][1-bit]; //以当前字符翻转结尾，翻转次数等于【i,j-1】结尾为bit的次数+1（翻转一次） dp[i][j][1-bit]=dp[i][j-1][bit]+1; //累加最小值 res+=Math.min(dp[i][j][bit],dp[i][j][1-bit]); } } System.out.println(res); } }

class main4{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int q=sc.nextInt(); while(q-->0){ double m=sc.nextInt(); double x=sc.nextInt(); if(x%m==0){ System.out.println((int)m); }else{ System.out.println((int)(x%m)); } } sc.close(); } }

class main5{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0){ int n=sc.nextInt();//数组长度 int k=sc.nextInt();//操作次数 //输入数组元素 int[]a=new int[n]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } //加减操作 for(int i=0;i<k;i++){ int u=sc.nextInt(); int v=sc.nextInt(); a[u-1]+=1; a[v-1]-=1; } //判断是否升序 boolean ok=true; for(int i=1;i<n;i++){ if(a[i]<a[i-1]){ ok=false; break; } } if(ok) System.out.println("Yes"); else System.out.println("No"); } sc.close(); } }

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.reflect.Array; import java.math.BigInteger; import java.util.*; //DP public class Main { static final int MOD=1000000007; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); long[]a=new long[n]; long sum=0; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); sum+=a[i]; } //dp[i][j] //从后往前，用j~n-1位置上的数，凑出总和为i的方案总数 long[][]dp=new long[(int)(sum+1)][n+1]; dp[0][n]=1;//凑出0只有一种方案，即空方案 //遍历要凑的总和 for(long i=1;i<=sum;i++){ //倒序遍历数组 //算j前必须先知道j+1的方案 for(int j=n-1;j>=0;j--){ long res=0; //枚举当前可选的数字 //在当前位置的后面还有n-1-j个位置没处理 //所选的数不能太大，综合推导为i-(n-1-j) for(long k=1;k<=i-(n-1-j);k++){ if(a[j]==k){//不能选和原数组上的元素一样的数 continue; } //剩下的和i-k由j+1位往后凑 //在j位置凑了k，剩下的i-k需要由后面的j+1~n-1去凑 res=(res%MOD+dp[(int)(i-k)][j+1])%MOD; } dp[(int)i][j]=res; } } System.out.println(dp[(int)sum][0]); } }

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.reflect.Array; import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); String s=sc.nextLine();//读取空行 //外层TreeMap：解决「按名字字典序排序 + 按名字分组」 //内层LinkedHashSet：解决「地址去重 + 保留插入顺序（主店地址）」 //商店名，地址集合 Map<String,Set<String>>map=new TreeMap<>(); for(int i=0;i<n;i++){ String[]meg=sc.nextLine().split(" "); String meg0=meg[0].toLowerCase(); String meg1=meg[1].toLowerCase(); //确保全小写输入 if(meg0.equals(meg[0])&&meg1.equals(meg[1])){ //getOrDefault如果商家名字不存在就新建一个空的 //LinkedHashSet按插入顺序保存元素，确保第一家是主店后面的是分店 Set<String>addr=map.getOrDefault(meg0,new LinkedHashSet<>()); addr.add(meg1);//set自动去重 map.put(meg0,addr); } } for(Map.Entry<String,Set<String>> entry:map.entrySet()){ System.out.println(entry.getKey()+" " +entry.getValue().iterator().next()+" " +(entry.getValue().size()-1)); } } }