因为期末周和放假回家休息了几天,今天开始继续

题目1:AcWing 4737.冰壶

红队和黄队进行了一场冰壶比赛，比赛结束后，裁判正在计算两队的得分。

场地可以看作一个二维平面，得分区域可以看作一个以 (0,0) 为圆心 Rh 为半径的圆。

场地上散落着 N 个红队的冰壶以及 M 个黄队的冰壶。

冰壶可以看作一个半径为 Rs 的圆。

每个冰壶的圆心坐标已知。
如果一个冰壶的任何部分位于得分区域的圆上或圆内（两者相切也算），则视为该冰壶位于得分区域内。
如果一个冰壶能够同时满足：

1
2
3
1.它位于得分区域内。

2.不存在任何对方冰壶比它距离得分中心 (0,0) 更近（欧几里得距离）。

那么，这个冰壶就是一个得分冰壶。

一个队伍的最终得分等于该队伍的得分冰壶数量。请你计算并输出两支队伍的最终得分。

一个冰壶与得分中心之间的距离等于其圆心点到点 (0,0)的距离。

数据保证不同冰壶与得分中心之间的距离不同，且冰壶两两之间不重叠（但可能相切）。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200010;



int main()
{
    int t;
    scanf("%d",&t);
    
    for(int i=1;i<=t;i++)
    {
        vector<double> a, b;//直接存得分圈内的圆壶的距离
        int rs,rh,n,m;//rs场地半径,rh圆壶半径,n,m圆壶数
        scanf("%d %d",&rs,&rh);
        scanf("%d",&n);
        for (int i=0; i<n; i++) 
        {
            int x, y;
            scanf("%d %d",&x,&y);
            double d = sqrt(x * x + y * y);
            if (d <= rs + rh) a.push_back(d);
        }
        scanf("%d",&m);
        for (int i=0; i<m; i++) 
        {
            int x, y;
            scanf("%d %d",&x,&y);
            double d = sqrt(x * x + y * y);
            if (d <= rs + rh) b.push_back(d);
        }
        
        int m1 = 0, m2 = 0;
        if (a.empty() || b.empty()) m1 = a.size(), m2 = b.size();
        else
        {
            sort(a.begin(), a.end());
            sort(b.begin(), b.end());
            for (auto d : a)
                if (d < b[0]) m1++;
                else break;
            for (auto d : b)
                if (d < a[0]) m2++;
                else break;
        }
        printf("Case #%d: %d %d\n",i,m1,m2);
    }
    
    
    return 0;
}

题目2:AcWing 4633.学生和导师

有 N 个学生（编号 1∼N）正在一起准备编程竞赛。

为了帮助彼此做好准备，每个学生都要选择一个其他学生作为他的导师，帮助其进步。
每个学生只能拥有一位导师，但是一个学生可以成为多个学生的导师。

第 i 个学生的实力评分为 Ri。

我们认为，导师不能比其受指导者强太多，所以只有当 Rj≤2×Ri 时，学生 j 才能成为学生 i 的导师。

请注意，导师的评分可以小于或等于其受指导者的评分。

毫不奇怪，每个学生都希望自己的导师尽可能强，所以对于每个学生，请你找出他们可以选择的导师的最高评分。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;

int a[N],b[N];

int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        memcpy(b,a,sizeof a);
        sort(b+1,b+1+n);
        printf("Case #%d: ",i);
        
        //用二分找大于2a[i]的第一个位置,然后对其--,就找到了
        //如果正好为自身,同样--,找到比自己拉的导师
        for(int i=1;i<=n;i++)
        {
            int l=1,r=n;
            while(l<r)
            {
                int mid=(l+r)>>1;
                if(b[mid]>2*a[i]) r=mid;
                else l=mid+1;
            }
            if(b[r]>2*a[i]) r--;//超出范围
            if(a[i]==b[r]) r--;//等于自身
            if(r!=0) printf("%d ",b[r]);
            else printf("-1 ");
        }
        printf("\n");

    }
    
    
    return 0;
}