wangruiyang

用户名：WangRY

访问量：2260

签　名：

等　　级
排　　名	3541
经　　验	1902
参赛次数	4
文章发表	5
年　　龄	22
在职情况	学生
学　　校	华中科技大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

重新排序——Java
浏览：144

技能升级——Java
浏览：415

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

技能升级——Java

　　作者: wangruiyang　　　　发表时间：2023-03-22 18:37:33 浏览：415　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-技能升级

# 前言

一开始我想到的是每次输入power和lose之后，我直接算出每个技能会被分成的各个部分，并存入arraylist中，之后排序arraylist，取前面的Math.min(m,arraylist.size())个大的元素相加得到最后的结果。

但是我错了。不论怎么优化，使用自带的Collection.sort()还是快速排序等等都会超出时间限制。

看来是思路出现了问题。这时候看到很多题解都介绍了二分查找的方法，简单看来下，发现其思路确实有很大的不同。

# 思路

二分查找是在要已经排好序的数据中找目标元素，但是我们这一题要找什么呢？

我们可以发现上面的思路的缺点在于对于每个元素，都将其每个分割的部分都算出来，并存起来，这是一个很大的开销。我们能不能找到第m个元素的值num_m，然后再对每个power依次减lose，如果发现剩下的power已经小于num_m，说明这个技能完全是不会用上的了。

有了上面的思路，剩下的就好办了。这里可以直接看代码。

值得注意的是确定了第m个元素是num_m之后，但是我们不知道num_m出现了多少次，可能它一共出现了10次，但是可能第m个是第3次，如果都直接把num_m的个数加上，可能会是的更大的power没有加上。代码中有更详细的过程。

# 代码

```java
import java.util.Scanner;

public class Main {
    public static long[] power;
    public static long[] lose;

public static int n;
    public static int m;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {

n = input.nextInt();
            m = input.nextInt();

power = new long[n];
            lose = new long[n];
            for (int i=0;i<n;i++) {
                power[i] = input.nextLong();
                lose[i] = input.nextLong();
            }

int left = 0, right = 1000000;
            long num_m = 0;     // 在0~1000000中找到在游戏中第m大的元素，为了缩小范围，num_m表示第m大的数值
            while (left<=right) {
                int mid = (left + right)/2;
                if (in_right(mid)) {     //说明要找的num_m在mid的右边
                    num_m = mid;      //num_m先记录下来了，因为比num_m大的元素已经足够m了
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
            // 此时已经找到了num_m，它就是第m大的数值
            // 但是我们不知道num_m出现了多少次，可能它一共出现了10次，但是第m个是第3次，如果都直接把num_m的个数加上，可能会是的更大的power没有加上。
            long sum = 0;
            long num = 0;    // 已经找到的点的个数
            for (int i=0;i<n;i++) {
                if (power[i] < num_m) {
                    continue;
                }

long k = 0;
                if ((power[i]-num_m)%lose[i]==0) {    // 表示num_m也算一个点，但是我们不能算上它
                    k = (power[i]-num_m)/lose[i];
                }
                else {                                // 表示num_m不算一个点，那么需要+1表示点数
                    k = (power[i]-num_m)/lose[i] + 1;
                }

sum += power[i] * k - lose[i] * (0 + (k-1))*k/2 ;
                num += k;
            }
            if (num < m) {
                sum += (m-num) * num_m;
            }
            System.out.println(sum);
        }

}
    // 假设k为第m大的数字，那么求存在多少数字是 >=k 的
    public static boolean in_right(long k) {
        long count = 0;
        for (int i=0;i<n;i++) {
            if (power[i]<k) {
                continue;
            }
            count += (power[i]-k)/lose[i] + 1;     // (power[i]-k)/lose[i]表示前面有几段，但是需要+1才能表示能加进去的点
        }
        return count >= m;
    }
}
```

# 其他

下面给出从大到小的快排代码。虽然本题没有用，但是相信后面可能会用到！

```java
public static void quickSort(ArrayList<Integer> al, int left, int right) {   // 从大到小
	int midNum = al.get(left);
	int i = left;
	int j = right;
	while (i!=j) {
		while (i<j && midNum>=al.get(j)) {
			j--;
		}
		al.set(i,al.get(j));
		al.set(j,midNum);

while (i<j && midNum<=al.get(i)) {
			i++;
		}
		al.set(j, al.get(i));
		al.set(i,midNum);
	}
	if (i > left+1) {
		quickSort(al, left, i-1);
	}
	if (j < right-1) {
		quickSort(al, j+1, right);
	}
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

wangruiyang

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

Hello, world! （C语言代码）

C二级辅导-同因查找（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

整除问题（C语言代码）

技能升级——Java

评论区

精彩推荐

C语言训练-阶乘和数* （C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

C语言程序设计教程（第三版）课后习题9.8 （Java代码）

A+B for Input-Output Practice (VI) （C++代码）

最小公倍数（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【金明的预算方案】（C++代码）

三角形（C语言代码）

The 3n + 1 problem （C语言代码）

wangruiyang

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

Hello, world! （C语言代码）

C二级辅导-同因查找 （C语言代码）

拆分位数 （C++代码）用char简单粗暴，嗯

整除问题 （C语言代码）

技能升级——Java

评论区

精彩推荐

C语言训练-阶乘和数* （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

C语言程序设计教程（第三版）课后习题9.8 （Java代码）

A+B for Input-Output Practice (VI) （C++代码）

最小公倍数 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【金明的预算方案】 （C++代码）

三角形 （C语言代码）

The 3n + 1 problem （C语言代码）

C二级辅导-同因查找（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

整除问题（C语言代码）

　　评论区

C二级辅导-等差数列（C语言代码）

最小公倍数（C语言代码）

【金明的预算方案】（C++代码）

三角形（C语言代码）