3168: 蓝桥杯2023年第十四届省赛真题-太阳(Java满分题解)

1302 阅读 3 评论 1 点赞

原题链接：蓝桥杯2023年第十四届省赛真题-太阳

###解题思路：线段按高度降序重排，然后投射到x轴上就成了区间覆盖问题。
### x轴上的端点将y=0代入y=kx+b可得x=-b/k，即(xY - Xy)/(Y - y),具体思路可以看参考代码
```java
import java.io.*;
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n = sc.nextInt();
    static int X = sc.nextInt();
    static int Y = sc.nextInt();

public static void main(String[] args){
        List<Triple> list = new ArrayList<>();
        for (int i = 0; i < n; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int l = sc.nextInt();
            list.add(new Triple(x , y , l));
        }  // 将所有x,y,l读入list中

list.sort(new Comparator<Triple>() {
            @Override
            public int compare(Triple l1, Triple l2) {
                return -Integer.compare(l1.y, l2.y);
            }
        });  // 以y从大到小排序

double[] arr1 = new double[2 * n];  // 保持以y从大到小排序的顺序进行在x轴上的覆盖
        double[] arr2 = new double[2 * n];  // 以在x轴上的坐标值排序，方便二分查找
        int i = -1;
        for(Triple item : list){
            arr1[++i] = arr2[i] =  y0x(item.x , item.y);
            arr1[n + i] = arr2[n + i] = y0x(item.x + item.l , item.y);
        }
        Arrays.sort(arr2);

boolean[] tree = new boolean[1 << 19];  // 将已覆盖的位置进行标记
        boolean f = false;
        int ans = 0;
        for (int j = 0; j < n; j++) {
            int l = Arrays.binarySearch(arr2 , arr1[j]);
            int r = Arrays.binarySearch(arr2 , arr1[j + n]);
            for (int k = l; k < r; k++) {
                if(!tree[k]){
                    tree[k] = true;
                    f = true;
                }
            }
            if(f){
                ++ans;
                f = false;
            }
        }
        System.out.println(ans);
    }

public static double y0x(int x , int y){
        if(x == X) return x;
        long a = (long) X * y;
        long b = (long) Y * x;
        return (b - a) / ((Y - y) * 1.0);
    }  // 返回端点在x轴上的投影
}

class Triple{
    int x , y , l ;

public Triple(int x , int y , int l){
        this.x = x;
        this.y = y;
        this.l = l;
    }
}
```

0.0分

4 人评分

本文分类：题解列表
浏览次数：1302 次浏览
发布日期：2023-11-07 14:40:16
本文链接：https://blog.dotcpp.com/a/99516

上一篇 > c代码记录之电报加密
下一篇 > c代码记录之自定义函数处理素数--C

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

3168: 蓝桥杯2023年第十四届省赛真题-太阳(Java满分题解)

评论列表共有 3 条评论

发表评论取消回复

3168: 蓝桥杯2023年第十四届省赛真题-太阳(Java满分题解)

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 3 条评论

发表评论 取消回复

评论列表共有 3 条评论

发表评论取消回复