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

柔光的暖阳◎ 2023-09-27 14:12 105阅读 0赞

**目录**

T1：P2694 接金币 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码：

分析：

T2:P1372 又是毕业季I - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码：

分析：

T3：P1106 删数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码：

分析：

T4:谈判 - 蓝桥云课 (lanqiao.cn)

代码：

分析：

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

### T1：[P2694 接金币 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2694 _ - _ _ _ _luogu.com.cn] ###

#### 代码： ####

package 蓝桥算法两周训练营__普及组.Day1;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2023-02-05 0:20
     */
    //P2694 接金币 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
    public class t1 {
        static class No implements Comparable<No> {
            int x;
            int y;
    
            No(int x, int y) {
                this.x = x;
                this.y = y;
            }
    
            @Override
            public int compareTo(No o) {
                return this.y - o.y;
            }
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int G = scanner.nextInt();
            for (int i = 0; i < G; i++) {
                int N = scanner.nextInt();
                boolean flag = true;
                ArrayList<No> list = new ArrayList<>();
                for (int j = 0; j < N; j++) {
                    int x = scanner.nextInt();
                    int y = scanner.nextInt();
                    No no = new No(x, y);
                    list.add(no);
                }
                Collections.sort(list);
                int x0 = 0;
                int y0 = 0;
                for (int j = 0; j < N; j++) {
                    int x1 = list.get(j).x;
                    int y1 = list.get(j).y;
                    if (Math.abs(x1 - x0) > Math.abs(y1 - y0)) {
                        flag = false;
                        break;
                    }
                    x0 = x1;
                    y0 = y1;
                }
                if (flag) {
                    System.out.println("Abletocatch");
                } else {
                    System.out.println("Notabletocatch");
                }
            }
        }
    }

![1a5a0ec4981a48c9b1448950a953b016.png][]

#### 分析： ####

> 1、重写比较方法，按y轴坐标从小到大进行排序，让y轴数值更小的即接到金币所花费时间更小的先接
> 
> 2、比较当前接到金币时到下一次接金币是否会超时，如果超时，则不能接到金币

### T2:[P1372 又是毕业季I - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1372 _I - _ _ _ _luogu.com.cn] ###

#### 代码： ####

package 蓝桥算法两周训练营__普及组.Day1;
    
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2023-02-05 0:20
     */
    public class t2 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            System.out.println(n/k);
        }
    }

![21542fa439214a5bac6d358e15d2ce0d.png][]

#### 分析： ####

> `题意是在n个数里面挑k个数使得其最大公约数最大`
> 
> `假如有9个人挑3个人使得其最大公约数最大应该怎么挑呢？显然是3 6 9`
> 
> `那么怎么输出该最大公约数呢？就是n/k`
> 
> `为什么？因为n/k是所选的人里面的最小数且是被选到的这些人里面的因子`
> 
> `例如,(n/k)*1, (n/k)*2, (n/k)*3 ... (n/k)*k,而最后一个数(n/k)*k一定是最接近n的数，这样才能保证公约数最大`

### T3：[P1106 删数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1106 _ - _ _ _ _luogu.com.cn] ###

#### 代码： ####

package 蓝桥算法两周训练营__普及组.Day1;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2023-02-05 0:20
     */
    
    /**
     * 芝士与你分享：s.erase(3,1);//从当前位置开始清除1个单位
     * 每次找到前面的数大于后面的数就要把前面的去掉，这样能使得删除部分数后最小
     * 为什么？比如132，我们删除3会变成12，删除1的话会变成32，12<32，所以应该按上述删
     */
    
    //P1106 删数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
    //https://www.luogu.com.cn/problem/solution/P1106?page=5
    public class t3 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String s = scanner.nextLine();
            int k = scanner.nextInt();
            int temp=k;
            char[] arr = s.toCharArray();
            ArrayList<Character> list = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                list.add(arr[i]);
            }
            int length=list.size();
            //删除数据操作
            while (k-- != 0) {
                for (int i = 0; i < list.size()-1 ; i++) {
                    if (list.get(i) > list.get(i + 1)) {
                        list.remove(i);
                        break;
                    }
                }
            }
    //        System.out.println(list.size());
    //        System.out.println(length);
            if(length!=list.size()+temp){
                for (int i = 0; i <length-temp ; i++) {
                    System.out.print(list.get(i));
                }
                return;
            }
    
            //去除前导零操作
            while (true){
                if(list.size()==1){//只剩最后一个数时直接退出
                    break;
                } else if (list.get(0) == '0') {
                    list.remove(0);
                } else {//当遇到一个非零数时，表示前导零已经不存在了，退出循环
                    break;
                }
            }
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i));
            }
        }
    }

![64fe5f1c95ec4089b896382a436cac6c.png][]

#### 分析： ####

> 1、删除数字：每次找到前面的数字大于后面的数字就删掉，删除一次就从新回到原点，循环删除k次
> 
> 2、去除前导零：因为题目说不改变数字的初始顺序，所以当出现001时，输出的为1，所以需要通过删除前导零这一操作
> 
> 3、注意特殊情况：
> 
> 数据是  
> 2567889  
> 3
> 
> 答案是
> 
> 2567

### T4:[谈判 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] ###

#### 代码： ####

package 蓝桥算法两周训练营__普及组.Day1;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2023-02-05 0:21
     */
    //https://www.lanqiao.cn/problems/545/learning/
    public class t4 {
    //题意要我们求最小，那显然是贪心题
    //样例输出是（1+3）+（1+3+5）+（1+3+5+9）=31
    //我们发现1和3出现3次，5出现2次，9出现1次
    //所以我们发现这道题需要让比较小的数加多点，较大的加少点，这样我们能使最后答案最小
    //假设a<b,显然a+b+b+b>a+a+a+b
    //所以我们需要排个序，然后进行花费计算
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n=scanner.nextInt();
            int[] arr=new int[n];
            int ans=0;
            for (int i = 0; i < n; i++) {
                arr[i]=scanner.nextInt();
            }
            Arrays.sort(arr);
            int count=arr[0];
            for (int i = 1; i < n; i++) {
                count+=arr[i];
                ans+=count;
            }
            System.out.println(ans);
        }
    }

![e6f01d8832a544d39dc7bd53b8aaf70e.png][]

#### 分析： ####

> 让最大的数出现的次数最少，一种典型贪心思想
> 
>  *  `//题意要我们求最小，那显然是贪心题`
>  *  `//样例输出是（1+3）+（1+3+5）+（1+3+5+9）=31`
>  *  `//我们发现1和3出现3次，5出现2次，9出现1次`
>  *  `//所以我们发现这道题需要让比较小的数加多点，较大的加少点，这样我们能使最后答案最小`
>  *  `//假设a<b,显然a+b+b+b>a+a+a+b`
>  *  `//所以我们需要排个序，然后进行花费计算`

[P2694 _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P2694
[1a5a0ec4981a48c9b1448950a953b016.png]: https://img-blog.csdnimg.cn/1a5a0ec4981a48c9b1448950a953b016.png
[P1372 _I - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P1372
[21542fa439214a5bac6d358e15d2ce0d.png]: https://img-blog.csdnimg.cn/21542fa439214a5bac6d358e15d2ce0d.png
[P1106 _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P1106
[64fe5f1c95ec4089b896382a436cac6c.png]: https://img-blog.csdnimg.cn/64fe5f1c95ec4089b896382a436cac6c.png
[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/545/learning/
[e6f01d8832a544d39dc7bd53b8aaf70e.png]: https://img-blog.csdnimg.cn/e6f01d8832a544d39dc7bd53b8aaf70e.png