阅读 101

AcWing第一场周赛题解

AcWing第一场周赛题解

题目链接:AcWing 3577. 选择数字

比最大值还大的值一定不再数组中,所以直接输出两个数组的最大值即可。

AC代码:

#include <iostream>#include <algorithm>using namespace std;int n, m;int x, a, b;int main(){    cin >> n;    for(int i = 0; i < n; i++)    {        cin >> x;        a = max(a, x);    }    cin >> m;    for(int i = 0; i < m; i++)    {        cin >> x;        b = max(b, x);    }    cout << a << ' ' << b << endl;    return 0;}

1|2B.最大中位数

题目链接:3578. 最大中位数

比赛的时候脑袋发抽,老是想用什么奇奇怪怪的方法做,加上刚刚学了对拍,对了一个多小时,发现暴力都写错了,菜死了。。。赛后发现,直接暴力遍历就行

首先肯定要排序的。排完序之后可以发现,从中位数开始,往后直接一个一个累加,并且一旦中位数和后面的数字相等了,就得一起同时累加,直到k无法满足将相等的数都加1为止。此时中位数即为最大中位数。(注意边界是2e9

AC代码:

#include <iostream>#include <algorithm>using namespace std;const int N = 2e5+10;int n, k;int a[N];int main(){    cin >> n >> k;    for(int i = 0; i < n; i++) cin >> a[i];    sort(a, a + n);    int p = n / 2;    a[n] = 2e9+10;    for(int i = p + 1; i <= n && k; i++)    {    	if(i - p <= k) 
    	{    	    int t = a[i] - a[p];    	    a[p] += min(t, k / (i - p)), k -= (i - p) * t;    	}    	else k = 0;    }	cout << a[p] << endl;        return 0;}

法二:二分

同样,我们只需要对排完后,中位数及其后面数进行操作。可以二分答案mid,将后半段小于mid的全部加到mid,然后判断操作是否小于k。二分出满足条件的最大值,即为最终答案。

AC代码:

#include <iostream>#include <algorithm>using namespace std;typedef long long LL;const int N = 2e5+10;int n, k;int a[N];bool check(int p){    LL sum = 0;    for(int i = n / 2; i < n; i++)        if(a[i] < p) sum += p - a[i];    if(sum > k) return false;    else return true;}int main(){    cin >> n >> k;    for(int i = 0; i < n; i++) cin >> a[i];    sort(a, a + 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;    }	cout << l << endl;        return 0;}

1|3C.数字移动

题目链接:3579. 数字移动

经过分析可以发现,如果将每一个数字看成一个顶点,可以移动看成一条有向边,则可以构成一个有向图。而且该有向图中,每一个顶点只有一条出边和一条入边。可以回到自己原本位置的路经一定是一个简单环。由此可以得出做法:求该图的所有强连通分量,答案即为所在强连通分量的点的数目。

进一步分析可以发现,所有的环可以看成一个集合,每一个数字需要的操作次数即为所在集合的大小。所以可以用维护集合大小的并查集做。

AC代码:

#include <iostream>#include <algorithm>using namespace std;const int N = 2e5+10;int t, n;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--)    {        scanf("%d", &n);        for(int i = 1; i <= n; i++) p[i] = i, s[i] = 1;        for(int j = 1; j <= n; j++)        {            int x;            scanf("%d", &x);            if(find(j) != find(x))            {                s[find(j)] += s[find(x)];                p[find(x)] = p[find(j)];            }        }        for(int i = 1; i <= n; i++)            printf("%d ", s[find(i)]);        puts("");    }        return 0;}


__EOF__

本文作者四谷夕雨

本文链接https://www.cnblogs.com/grain-rain/p/14826467.html

文章分类
后端
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐