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;
}