AcWing第一场周赛题解
A.选择数字
题目链接: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;
}
B.最大中位数
题目链接: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;
}
C.数字移动
题目链接: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;
}