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%