Codeforces-Round-610-Div2部分题解

发表于 | 更新于 | 阅读次数：

比赛链接

时隔10天的CF，打得还是很自闭

A.Temporarily unavailable

题意：

一根坐标轴，三个点a,b,c,一个半径r。以c为中心的，半径为r的部分不算入结果，a，b之间的段算入结果。

分析：显然，只有六种情况，分情况处理即可。（十分钟写出来还行）

Code:

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int main()
{
    int n;
    int t;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,c ,r;
        scanf("%d%d%d%d",&a,&b,&c,&r);
        int lc,rc;
        lc=c-r;
        rc=c+r;
        if(a>b)
            swap(a,b);
        if(lc>=b||rc<=a)
        {
            printf("%d\n",b-a);
        }
        else if(lc>=a&&rc<=b)
        {
            printf("%d\n",b-a-r*2);
        }
        else if(lc<=a&&rc>=b)
        {
            {
                printf("0\n");
            }
        }
        else if(lc<=a&&rc>=a&&rc<=b)
        {
            //if(lc<=a&&rc>=a&&rc<=b)
            {
                printf("%d\n",b-rc);
            }
        }
        else
        {
            printf("%d\n",lc-a);
        }
    }
    return 0;
}

B1.K for the Price of One (Easy Version)

题意：

n件物品（各有各的价格，记为a_i)，p元钱，如果购买一个物品，可以选择仅购买本体，亦可以选择再拿走k-1个价格小于或等于该物品的其他物品，每个物品仅可选择一次。

分析：

easy版限定k为2，显然，我们可以从第k个或者第k+1个开始处理，可以保证覆盖所有情况。

Code:

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
56
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int a[maxn];

int main()
{
    int n;
    int t;
    scanf("%d",&t);
    while(t--)
    {

        int p,k;
        scanf("%d%d%d",&n,&p,&k);
        for(int i=0 ; i<n ; i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int ans1,ans2;
        ans1=1;
        ans2=0;
        int p1=a[0],p2=0;
        for(int i=2 ; i<n&&p1<=p-a[i] ; i+=2 )
        {
            p1+=a[i];
            ans1+=2;
        }
        for(int i=1 ; i<n&&p2+a[i]<=p ; i+=2 )
        {
            p2+=a[i];
            ans2+=2;
        }
//        printf("%d\n",ans1);
//        printf("%d\n",ans2);
        if(ans1==1&&p<a[0])
            ans1=0;
        printf("%d\n",max(0,max(ans1,ans2)));
    }

    return 0;
}
/*
4 20 2
10 10 10 10

*/

B2.K for the Price of One (Hard Version)

见代码吧，搭配注释，开袋即食：
总感觉这个代码还可以被HACK，但是就AC了，而且我推不出会超时的样例，无奈。。。。

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
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 7;
typedef long long ll;
int a[maxn], ans[maxn];
ll pp[maxn];
int main()
{
    int t;
    int n, p, k;
    cin >> t;
    while (t--)
    {
        cin >> n >> p >> k;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]); //a[i] 最大为10000
        }
        sort(a, a + n);
        int aa = 0;
        for (int i = 0; i < k; i++) //分为K种情况，直接遍历处理，第一种情况是以第K小的元素，以此类推
        {
            pp[i] = 0; //先处理可以使用优惠的
            ans[i] = 0;
            int en = i, be = 0;
            for (int j = i + k - 1; j < n && pp[i] + a[j] <= p; j += k)
            {
                pp[i] += a[j];
                ans[i] += k; //直接带走K件东西
                en = j + 1;
            }
            int yu = p - pp[i]; //剩余的钱，看看是否还可以买一些东西

            while (be < i && yu - a[be] >= 0)
            {
                yu -= a[be];
                be++;
                ans[i]++;
            }

            while (en < n && yu - a[en] >= 0)
            {
                yu -= a[en];
                en++;
                ans[i]++;
            }
            aa = max(aa, ans[i]);
            if (aa == n) //减少无用运算
                break;
        }
        printf("%d\n", aa);
    }
    return 0;
}
/*
1
200000 2000000000 200000
1 10000 10000 * 19998 2000000001

1
10000 9999 9999
1*9999 10000

*/

0%