Codeforces Round 844 A-B题解

2023/1/15 算法竞赛 题解 C++ Codeforces Round 844 Div. 1+Div. 2

😥

A. Parallel Projection

题面

因为路径是与坐标轴平行的，所以可以看出只有四条可能的路径(前后左右)，都算一遍取最小即可.

AC代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int w,d,h;
        cin>>w>>d>>h;
        int a,b,f,g;
        cin>>a>>b>>f>>g;
        int ans1=abs(f-a)+h+min(b+g,2*d-b-g);
        int ans2=abs(b-g)+h+min(a+f,2*w-a-f);
        cout<<min(ans1,ans2)<<'\n';
    }
    return 0;
}

B. Going to the Cinema

题面

可以感觉出来需要排序，先把 ai 排成升序(有 i < j时，ai < aj ).

若 i < j ，则j去的话i必然也去.换言之，去的人的集合只可能是 { 1, 2, ..., k }, (0≤k≤n) .

特别地，若 ai = 0 ，则i必须去.

枚举一下即可

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        a[n+1]=1e9;
        int ans=0;
        int t=1;
        if(a[1]!=0)     //判一下是否可能全不去
            ans++;
        while(t<=n)
        {
            while(a[t]>=t)
                t=a[t]+1;
            while(a[t]<t)
                t++;
            ans++;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
img_show