链接：https://ac.nowcoder.com/acm/problem/213140来源：牛客网首次思路：在遍数限制范围内，每次都把数组内最大的偶数除以2，最后直接计算元素总和但是错误在于原代码的外层循环是 for(int i=0;i<k;i++)，内层循环遍历整个数组（O(n)），整体时间复杂度是 O(k×n)。但题干中 k 最大可达 10^9，n 最大 10^5，k×n 会达到 10^14—— 这是绝对无法在规定时间内跑完的（计算机每秒最多处理 10^8 次操作），必然超时。举个例子：若 k=10^9，原代码需要循环 10^9 次，即使每次循环只花 1 纳秒，也需要 1 秒（实际每次循环远不止 1 纳秒），更别说还要加内层的 10^5 次遍历。import java.util.Scanner;public class Main{public static void main(String[] args) {/*** 除以2* https://ac.nowcoder.com/acm/problem/213140*///输入Scanner in = new Scanner(System.in);int n=in.nextInt();int k=in.nextInt();int []a=new int [n+1];for(int i=1;i<=n;i++){a[i]=in.nextInt();}//业务逻辑int sum=0;for(int i=0;i<k;i++){//外层循环：次数Boolean flg=false;int j=1;int max_j=0; int max=0;for( j=1;j<=n;j++){//内存循环：数组if(a[j]%2!=0){//只操作偶数continue;}if(a[j]>max){max=a[j];max_j=j;}if(max==0){flg=true;break;}}a[max_j]=max/2;//已经找到了最大的数if(flg==true)//如果所有数都等于0，直接结束循环{break;}}for(int i=1;i<=n;i++){sum+=a[i];}System.out.println(sum);}}时间复杂度高的原因在于一个大偶数可能会被操作多次，但它仍是最大的数，并不需要重复遍历数组。因此，用最大堆存储当前所有偶数，每次从堆中取出最大的偶数，计算它能被操作的 “最大次数”（直到变成奇数或 k 用尽），批量处理后更新堆和剩余操作次数，将时间复杂度从 O(k×n) 降到 O(n log n + m log n)（m 是堆的操作次数，远小于 k）/*** 除以2* 使用堆来处理大量的数据，不会超时*/public static void test3_2(){//使用堆的版本/*** 失败的代码使用了int类型存储总和sum和输入数据x，而通过的代码使用了long类型：* 当输入数据较大（例如超过int的最大值2^31-1）时，int类型会发生溢出，导致计算结果错误。* 题目中没有限制数据范围，使用int必然会在大数据测试用例中失败，而long能处理更大的数值范围。*/Scanner in = new Scanner(System.in);int n=in.nextInt();int k=in.nextInt();//构建最大堆//Greater greater=new Greater();//        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(greater);PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((a,b)->{return b-a;});long sum=0,x;for(int i=0;i<n;i++){//循环结束就自动计算总和x=in.nextLong();if(x%2==0){priorityQueue.offer((int)x);//输入的数据直接存进堆里}sum=sum+x;}for(int i=0;i<k;i++){if(priorityQueue.isEmpty()){break;}int num=(int)priorityQueue.poll()/2;sum=sum-num;if(num%2==0){priorityQueue.offer(num);}}System.out.println(sum);}

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class PalindromeList { public boolean chkPalindrome(ListNode A) { // write code here ListNode f=A,s=A; while(f!=null&&f.next!=null){ s=s.next; f=f.next.next; } //f是中...

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Partition { public ListNode partition(ListNode pHead, int x) { // write code here if(pHead==null){ return null; } ListNode head=new ListNode(0); head.next=pHead; ListN...

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Partition { public ListNode partition(ListNode pHead, int x) { // write code here ListNode s=new ListNode(0); ListNode b=new ListNode(0); ListNode pre=pHead,p=pHead; L...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return int整型 */ public int LastRemaining_Solution (int n, int m) { // write code here int f=0; for(int i=2;i<=n;i++){ f=(f+m)%i; } return f; } } 也可以使用环形链表来模拟这一过程，但是时间复杂度...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param grid int整型ArrayList<ArrayList<>> * @return int整型 */ public int rotApple (ArrayList<ArrayList<Integer>> grid) { //上下左右 int []dx={0,0,-1,1}; int []dy={-1,1,0,0}; int ret=0; int m...

import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); List<List<Integer>>arr=new ArrayList<>(); List<Integer>pre=new ArrayList<>(); for(int i=0;i<n;i++){ List<Integer> line=new Arr...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param board string字符串一维数组 * @param word string字符串 * @return bool布尔型 */ //上下左右 int []dx={0,0,-1,1}; int []dy={-1,1,0,0}; boolean vis[][]; char[]word; int m,n; public boolean exist (String[] board, String _wo...

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int a=0,b=1,c=a+b; while(n>c){ a=b; b=c; c=a+b; } System.out.println(Math.min(n-b,c-n)); } }  import java.util.Scanne...

输入：5 32 4 8 10 11输出：24说明：对8操作2次，对10操作1次，最后的数组是2 4 2 5 11。可以证明这样的操作是最优的。我的初始思路是直接遍历找出数组最大的偶数，直接计算，但是超时了，以下是第一次写的代码 /** * 除以2 * https://ac.nowcoder.com/acm/problem/213140 */ public static void test3_1(){ /** * 做法一：普通思路，没有使用堆，超时了 */ //输入 Scanner in = new Scanner(System.in); int n=in.nextInt(); int k=in...

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { /** * 滑动窗口 * 解决问题：解决数组、字符串的连续子区间问题 * 使用条件：每个值都大于0（满足单调性） */ /** * 下...

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String[]arr=in.nextLine().toUpperCase().split(" "); StringBuilder stringBuilder=new StringBuilder(); for(int i=0;i<arr.length...