暑假作业竟然如此芳香（hdu4145枚举+贪心）

爱被打了一巴掌 2021-12-11 02:01 174阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=4145][http_acm.hdu.edu.cn_showproblem.php_pid_4145]

题目：在一个坐标系上，有许多敌人，现在有两个火力范围是圆形的炮塔，如何才能在火力能覆盖所有人的情况下还能使两炮塔半径R1,R2的平方和R1^2+R2^2最小？

思路：一开始没搞明白，直接简单粗暴的想算出每个敌人到两炮台的距离，用这么一个转移方程来算

![1559300-20190705000556246-476262798.png][]

大意就是dp(i)表示第i个敌人所产生的最小费用,后来发现这道题每次决策都会相互影响，不能用这种动规的思想去写，百度了下还是直接贪心+枚举，只需要算出每个敌人到两个炮台的距离，其中一个炮台从大到小枚举，另外一个炮台从前一个炮台火力不能达到的范围枚举，维护一个最小值就可以了。

代码如下

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const int maxn = 100010;
     4 struct point {
     5     int x;int y;int da;int db;
     6 } c[maxn];
     7 bool cmp(point a,point b){
     8     return a.da<b.da;
     9 }
    10 int main() {
    11     int t;
    12     scanf("%d",&t);
    13     while(t--) {
    14         int x1,y1,x2,y2;
    15         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    16         int n;
    17         scanf("%d",&n);
    18         for(int i=0;i<n;++i){
    19             scanf("%d%d",&c[i].x,&c[i].y);
    20             int x=c[i].x,y=c[i].y;
    21             c[i].da=(x-x1)*(x-x1)+(y-y1)*(y-y1);
    22             c[i].db=(x-x2)*(x-x2)+(y-y2)*(y-y2);
    23         }
    24         sort(c,c+n,cmp);
    25         int min_d = c[n-1].da;
    26         int tmp=0;
    27         for(int i=n-2;i>=0;--i){
    28             tmp=max(tmp,c[i+1].db);
    29             min_d=min(min_d,tmp+c[i].da);
    30         }
    31         tmp=max(tmp,c[0].db);
    32         min_d=min(min_d,tmp);
    33         printf("%d\n",min_d);
    34     }
    35     return 0;
    36 }

转载于:https://www.cnblogs.com/mlcn-2000/p/11135904.html

[http_acm.hdu.edu.cn_showproblem.php_pid_4145]: http://acm.hdu.edu.cn/showproblem.php?pid=4145
[1559300-20190705000556246-476262798.png]: /images/20211210/3357df1b6ee745988a967970384abcec.png