relife

用户名：re1ife

访问量：541

签　名：

等　　级
排　　名	23690
经　　验	630
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	西南石油
专　　业

　　自我简介：

TA的其他文章

前缀和 + 二分
浏览：490

你可能喜欢

前缀和 + 二分

　　作者: relife　　　　发表时间：2023-02-23 16:33:34 浏览：490　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-最少刷题数

# 前缀和 + 二分

先看测试数据范围 10^5, 暴力会TLE。

先将每个人刷题的数量保存，并且更新最多刷题数量

`sum[i]`来存放刷题数目不超过i个人数，

因此可以得到公式

比我卷的人` more = n -  sum[nums[i]]`
比我躺的人` less = sum[ nums[i]- 1]`

当more <= less 直接躺平。
MORE > less也就是说卷过我的人呢大于躺于我的人， 那我也开卷。

因为我多写了一些题目，所以 [sum[num[1]], sum[now]) 会减少1个 但是由于我目前是写了now道题，所以sum[now] - 1 + 1不变

```java
import java.io.*;
import java.util.*;
        
public class Main {
    static BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static int readInt() throws  Exception{
        reader.nextToken();
        return (int) reader.nval;
    }
        
    public static String readString() throws  Exception{
        reader.nextToken();
        return reader.sval;
    }
    static int n;
    static int []nums = new int[100020];
    static int []sum = new int[100020];
    public static void main(String[] args) throws Exception{
        n = readInt();
        int maxs = 0;
        for(int i = 0; i < n;i++) {
            maxs = Math.max(nums[i] = readInt(),maxs);

sum[nums[i]]++;
        }
        
        for(int i = 1; i <= maxs+1;i++){
            sum[i] += sum[i-1];
        }
        
        for(int i = 0; i < n;i++){
            int count = 0;
            int less  = 0 ,more = 0;
            if(nums[i]>0){
                less = sum[ nums[i]- 1];
                more = n -  sum[nums[i]];
                if(more <= less ){
                
                    writer.write("0 ");
                    continue;
                 }
            }
            int l = nums[i],r  = maxs;

while(l < r){
                int mid =  l +  r >> 1;
                if(chexck(mid)) r = mid;
                else l = mid + 1;

}

writer.write(l - nums[i] +" ");
            
        }
        writer.flush();
    }

private static boolean chexck(int mid) {
        int less = sum[ mid - 1] - 1;
        int more = n -  sum[mid];
        return more <= less;
    }
}
```

0.0分

7 人评分

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

relife

TA的其他文章

你可能喜欢

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

母牛的故事（C语言代码）

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

C语言训练-斐波纳契数列（C语言代码）

C二级辅导-进制转换（C语言代码）

前缀和 + 二分

评论区

精彩推荐

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

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

C语言训练-立方和不等式（C语言代码）

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

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

1071题解

Hello, world! （C语言代码）

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

【计算直线的交点数】（C语言代码）

简单的a+b （C语言代码）

relife

TA的其他文章

你可能喜欢

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

母牛的故事 （C语言代码）

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

C语言训练-斐波纳契数列 （C语言代码）

C二级辅导-进制转换 （C语言代码）

前缀和 + 二分

评论区

精彩推荐

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

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

C语言训练-立方和不等式 （C语言代码）

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

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

1071题解

Hello, world! （C语言代码）

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

【计算直线的交点数】 （C语言代码）

简单的a+b （C语言代码）

母牛的故事（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

C语言训练-立方和不等式（C语言代码）

【计算直线的交点数】（C语言代码）