蓝桥算法两周训练营--Day4

客官°小女子只卖身不卖艺 2023-09-27 14:22 105阅读 0赞

**目录**

T1：P1115 最大子段和 - 洛谷

代码：

解析：

T2：P1678 烦恼的高考志愿 - 洛谷

代码：

解析：

课后练习：

--------------------

### T1：[P1115 最大子段和 - 洛谷][P1115 _ -] ###

#### 代码： ####

package 蓝桥算法两周训练营__普及组.Day4;
    
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2023-02-08 14:42
     */
    public class t1_前缀和 {
        /**
         * 时间O（n），空间O（1）
         * 思路：用now记录当前读入的数据
         * tmp是当前的子段和，ans是当前最大子段和
         * 若tmp<0，则重置为0
         * 因为如果后面有大数，则0+大数肯定比负数+大数要大
         * ans初值为第一个now，不然如果全部为负数就会有bug
         * 也可以置为很小的一个数
         * @param args
         */
        //    P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n=scanner.nextInt();
            int[] nums=new int[n+1];
            // 如果初始值ans设为0的话，当输入值全为负数的时，输出的ans还为0，会出现错误）
            int ans=-1001;//存放最大前缀和（初始值设为负数）
            int temp=0;//存放每个子前缀和
            for (int i = 1; i <=n ; i++) {
                nums[i]=scanner.nextInt();
                temp+=nums[i];
                if(temp>ans) {//如果ans初始值置为0，当temp为负数时，就会放生错误
                    ans = temp;
                }
                if(temp<0)temp=0;
            }
            System.out.println(ans);
        }
    }

#### 解析： ####

> 见代码

![1be44de81d6448cbb40e78943d346222.png][]

### T2：[P1678 烦恼的高考志愿 - 洛谷][P1678 _ -] ###

#### 代码： ####

package 蓝桥算法两周训练营__普及组.Day4;
    
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2023-02-08 16:43
     */
    public class t2_100分 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int m = sc.nextInt();
            int n = sc.nextInt();
            int[] school = new int[m + 1];
            int[] stu = new int[n + 1];
            for (int i = 1; i <= m; i++)
                school[i] = sc.nextInt();
            for (int j = 1; j <= n; j++)
                stu[j] = sc.nextInt();
    
            Arrays.sort(school, 1, m + 1);
    
            int ans = 0, x = 0;
            for (int i = 1; i <= n; i++) {
                int left = 1, right = m;
                while (left < (right - 1)) {//这样能保证学生成绩在两个学校之间，如果是left<right，得到的就会是left==right
                    int mid = (left + right) / 2;
                    if (stu[i] >= school[mid]) {
                        left = mid;
                    } else right = mid;
                }//找到学生估值所在哪两个学校的录取分数线之间
                x = Math.min(Math.abs(stu[i] - school[left]), Math.abs(school[right] - stu[i]));
                ans += x;
            }
            System.out.print(ans);
        }
    }

#### 解析： ####

> 见代码

![00be1b6407bd41c7bf52aa6a12c7c652.png][]

#### 课后练习： ####

> T3：[P1873 砍树 - 洛谷][P1873 _ -]
> 
> T4：[519. 跳石头 - AcWing题库][519. _ - AcWing]

[P1115 _ -]: https://www.luogu.com.cn/problem/P1115
[1be44de81d6448cbb40e78943d346222.png]: https://img-blog.csdnimg.cn/1be44de81d6448cbb40e78943d346222.png
[P1678 _ -]: https://www.luogu.com.cn/problem/P1678
[00be1b6407bd41c7bf52aa6a12c7c652.png]: https://img-blog.csdnimg.cn/00be1b6407bd41c7bf52aa6a12c7c652.png
[P1873 _ -]: https://www.luogu.com.cn/problem/P1873
[519. _ - AcWing]: https://www.acwing.com/problem/content/521/