C/C++教程

AcWing第1场周赛 -2021/5/29

本文主要是介绍AcWing第1场周赛 -2021/5/29,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 

3577.移动数字

题目描述

给定一个整数数组 A,其包含 n 个正整数 a1,a2,…,an 以及一个整数数组 B,其包含 m 个正整数 b1,b2,…,bm。

请从数组 A 中挑选一个元素 a 并从数组 B 中挑选一个元素 b,使得 a+b 既不包含于 A 也不包含于 B。

例如,如果 A=[2,1,7] 而 B=[1,3,4],则可以从 A 中选取 1,从 B 中选取 4,这样得到的数字 1+4=5 既不在 A 中,也不在 B 中。

但是,我们不能从 A 中选取 2,从 B 中选取 1,因为得到的数字 2+1=3 包含于 B。

可以证明这样的数对一定存在,如果答案不唯一则输出任意合理答案均可。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,…,an。

第三行包含整数 m。

第四行包含 m 个整数 b1,…,bm。

输出格式

共一行,输出 a 和 b,中间用空格隔开。

数据范围

对于 30% 的数据,1≤n,m≤10
对于 100% 的数据,1≤n,m≤100,1≤ai,bi≤200

输入样例1:

1
20
2
10 20

输出样例1:

20 20

输入样例2:

3
3 2 2
5
1 5 7 7 9

输出样例2:

3 1

输入样例3:

4
1 3 5 7
4
7 5 3 1

输出样例3:

1 1

题目分析

这道题数据范围比较小暴力搜索就可以
我们这里用个小技巧
两次遍历分别找出两个数组A中的最大值x和数组B中的最大值y
那么x+y一定即不再A中也不在B中
直接输出就可以了

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

int n,m;

int main(){
    cin>>n;
    int x=0,y=0;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        x=max(x,a);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int b;
        cin>>b;
        y=max(b,y);
    }
    cout<<x<<' '<<y<<endl;
    return 0;

}

3578.最大中位数

题目描述

给定一个由 n 个整数组成的数组 a,其中 n 为奇数。

你可以对其进行以下操作:

选择数组中的一个元素(例如 ai),将其增加 1(即,将其替换为 ai+1)。
你最多可以进行 k 次操作,并希望该数组的中位数能够尽可能大。

奇数长度的数组的中位数是数组以非降序排序后的中间元素。

例如,数组 [1,5,2,3,5] 的中位数为 3

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出一个整数,表示通过操作可能得到的最大中位数。

数据范围

对于 30% 的数据,1≤n≤5。
对于 100% 的数据,1≤n≤2×105,1≤k≤109,1≤ai≤109。

输入样例1:

3 2
1 3 5

输出样例1:

5

输入样例2:

5 5
1 2 1 1 1

输出样例2:

3

输入样例3:

7 7
4 1 2 4 3 4 4

输出样例3:

5


算法1

(贪心+左右指针) O(nlogn)O(nlogn)

这道题首先我们将整个数组
然后我们定义一个左右指针l,r
定义n=数组大小-1

左指针l指向中位数所在下标
右指针r指向中位数右边(包括中位数本身)最后一个等于中位数的下标 (l<=r<=n)

这样我们的左右指针就是一个区间

每次循环我们都把区间内所有的数 +1 这样我们的中位数就 +1 同时 k要减去 r-l+1

当 k==0 或者 k<r-l+1 (不够区间内所有值都+1) 的时候循环停止 此时的中位数就是我们要求的中位数

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6+10;

typedef long long LL;

int n,k;
int a[N];

int seekR(int q[],int r){  //寻找右端点
    int res=r;
    int flag=0;
    for(int i=r;i<=n;i++){
        if(q[r]==q[i]){
            continue;
        }
        else{
            flag=1;
            res=i-1;
            break;
        }
    }
    if(flag==0){
        res=n;
    }

    return res;

}


int main(){
    cin>>n>>k;

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    if(n==1){
        cout<<k+a[1]<<endl;
        return 0;
    }
    sort(a+1,a+n+1);


    int l=(n/2)+1;
    int r=seekR(a,l);
    int num=a[l];

    while(k && k>=r-l+1){

        num++;
        k-=r-l+1;
        a[r]=num;
        r=seekR(a,r);
    }

    cout<<num<<endl;

    return 0;
}

算法2

(二分) O(nlongn)O(nlongn)

当时做题的时候并没有想到二分
这种方法是参考别人的

我们每次从 1 到 2e9 中二分查找答案
这里解释一下右端点为什么是 2e9 :
因为题目给出的范围 1<=k<=1e9,1<=w[i]<=1e9 如果说k==1e9 n==1 w[0]== 1e9 的时候
要找的答案就是1e9+1e9 也就是我们右端点的最大值

参考代码

https://www.acwing.com/activity/content/code/content/1300036/

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long LL;

using namespace std;

const int N = 2e5+10;

int n,k;
int w[N];

bool check(int mid){
    LL res=0;
    for(int i=n/2;i<n;i++){
        if(w[i]<mid)
            res+=mid-w[i];
    }
    return res<=k;
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) scanf("%d",&w[i]);
    sort(w,w+n);
    int l=0,r=2e9;
    while(l<r){
        int mid=(LL)l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",r);
    return 0;
}

 

3577.移动数字

 

题目描述

将 1∼n 按顺序排成一排,构成一个数列。

数字 i 刚好位于位置 i。

再给定一个长度为 n 的位置序列 p1,p2,…,pn,它是 1∼n 的一种排列。

接下来,我们会重复不断地对数列进行如下操作:

重新排列数列中每个数的位置,将位于位置 i 的数移动至位置 pi。(如果 i=pi 则该数仍移动至位置 i)。
每次操作开始时,所有数的移动同时进行,操作结束后,数列将变为一个新的 1∼n 的排列。
例如,当 n=6 并且 p=[4,6,1,3,5,2] 时,第一次操作后,数字 1 将移动至位置 4,数字 2 将移动至位置 6,以此类推;第二次操作后,数字 1 将移动至位置 3,数字 2 将移动至位置 2,以此类推。

你的任务是确定从 1 到 n 的每个数字 i,经过多少次操作后,第一次重新回到位置 i。

例如,考虑 p=[5,1,2,4,3],数字 1 的移动轨迹如下:

第一次操作后,到达位置 5。
第二次操作后,到达位置 3。
第三次操作后,到达位置 2。
第四次操作后,回到位置 1。
所以,经过四次操作后,数字 1 第一次回到位置 1。

值得一提的是,数字 4 经过一次操作后就回到了位置 4.

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据第一行包含整数 n。

第二行包含 n 个整数 p1,…,pn。

输出格式

每组数据输出一行结果,包含 n 个整数,其中第 i 个整数表示数字 i 第一次回到位置 i 所经过的操作次数。

整数之间用单个空格隔开。

数据范围

对于 30% 的数据,1≤T≤10,1≤n≤10。
对于 100% 的数据,1≤T≤1000,1≤n≤2×105,1≤pi≤n。
保证 p1∼pn 是 1∼n 的一种排列。
保证 ∑n≤2×105(一个输入中的 T 个 n 相加之和不超过 2×105)。

样例

输入样例:

6
5
1 2 3 4 5
3
2 3 1
6
4 6 2 1 5 3
1
1
4
3 4 1 2
5
5 1 2 4 3

输出样例:

1 1 1 1 1
3 3 3
2 3 3 2 1 3
1
2 2 2 2
4 4 4 1 4


算法1

(并查集求连通块个数)

参考文献

https://www.acwing.com/activity/content/code/content/1300090/

https://www.acwing.com/problem/content/839/

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n,T;
int p[N],s[N];

int find(int x){  //并查集+路径压缩
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){  //初始化
            p[i]=i;
            s[i]=1;
        }
        for(int i=1;i<=n;i++){
            int j;
            cin>>j;
            if(find(i)!=find(j)){
                s[find(j)]+=s[find(i)];
                p[find(i)]=find(j);
            }
        }
        for(int i=1;i<=n;i++){
            printf("%d ",s[find(i)]);
        }
        puts(" ");
    }
    return 0;
}


这篇关于AcWing第1场周赛 -2021/5/29的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!