题目1：选择数组
方法1：取a数组最大值和b数组最大值，可以确定a+b一定不在a和b中，因为元素都大于0
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n, m, t, mx1 = 0, mx2 = 0;
cin >> n;
for(int i = 0; i < n; i++) cin >> t, mx1 = max(mx1, t);
cin >> m;
for(int i = 0; i < m; i++) cin >> t, mx2 = max(mx2, t);
cout << mx1 << ' ' << mx2 << endl;
return 0;
}
方法2：取标记数组vis，记录a和b出现的值，枚举所有a+b，判断是否不在vis中，可以适用于负数元素
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
int mp[N<<1], a[N], b[N], n, m;
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]), mp[a[i]]=1;
cin >> m;
for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]), mp[b[i]]=1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!mp[a[i]+b[j]]) {
printf("%d %d\n", a[i], b[j]);
return 0;
}
}
}
return 0;
}
题目2：最大中位数
比赛时的超时代码
- 思路是先对数组排序
- 大根堆记录前n/2个数组元素，小根堆记录剩下的所有元素
- 如果大根堆的堆顶小于小根堆的堆顶，就可以对大根堆的堆顶元素+1,
- 如果大根堆的堆顶大于等于小根堆的堆顶，只能对小根堆的堆顶元素+1
这样可以保证能增大中位数时一定增大中位数，但是会超时，因为每次操作是$log(n)$的，而操作次数最多是$10^9$…
// 大根堆+小根堆
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
priority_queue<int> mx;//大根堆
priority_queue<int, vector<int>, greater<int>> mi;//小根堆
const int N = 2e5+10;
int n, k, a[N];
int main()
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i ++ ) { scanf("%d", &a[i]); }
if(n == 1) {
printf("%d\n", a[0]+k);
return 0;
}
// 注意下面不适用于1个数的情况
sort(a, a+n);
for(int i = 0; i <= n/2; i++) { mx.push(a[i]); }
for(int i = n/2+1; i < n; i++) { mi.push(a[i]); }
for(int i = 0; i < k; i++) {
if(mx.top() < mi.top()) {
int t = mx.top();
t++;
mx.pop();
mx.push(t);
}
else {
int t = mi.top();
t++;
mi.pop();
mi.push(t);
}
}
printf("%d\n", mx.top());
return 0;
}
方法1：二分
- 对数组进行升序排序
- 转求值为判定，二分最大中位数的值
- 每次二分判断当前中位数是否合法
/*
二分：转求值为求合法性
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int n, k, a[N];
// 2e9不会爆int，3e9才会
// 256MB可以开67108864即8位数，7个0的int型数组
// x表示中位数的值是否合法
bool check(int x)
{
LL sum = 0; // 需要+1多少次才能保证x是合法的
for(int i = n/2; i < n; i++) sum += max(0, x-a[i]);
return sum <= k;//+1的次数必须小于等于题目给定的次数k
}
int main()
{
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a+n);//求中位数很容易想到排序
int L = 1, R = 2e9;//最大化中位数，左半部分的元素肯定不会改变，关键是保证右半部分合法
while(L < R) {
int mid = (LL)L+R+1>>1;
// printf("%d %d %d\n", L, R, mid);
if(check(mid)) L = mid;
else R = mid-1;
}
cout << L << endl;
return 0;
}
题目3数字移动
连模拟都整不明白的我
参考的模拟代码
暴力
// 画出转移路径后可知，问题就是求简单环的大小
// 环上点的操作次数都相等
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5+10;
int p[N], vis[N], res[N];
int main()
{
int T, n;
scanf("%d", &T);
while(T--) {
memset(vis, 0, sizeof vis);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
vector<int> v;
for(int j = i; !vis[j]; j = p[j]) {
v.push_back(j);
vis[j] = true;
}
for(int x : v) res[x] = v.size();
}
}
for(int i = 1; i <= n; i++) printf("%d ", res[i]);
printf("\n");
}
return 0;
}
并查集维护size
// 画出转移路径后可知，问题就是求简单环的大小
// 环上点的操作次数都相等
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5+10;
int p[N], fa[N], sz[N];
int T, n;
int find(int x) {
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
fa[x] = y, sz[y] += sz[x];
}
void init() {
for(int i = 1; i <= n; i++) {
fa[i] = i, sz[i] = 1;
}
}
int main()
{
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
init();
// 通过并查集维护环和环的大小
for(int i = 1; i <= n; i++) {
merge(i, p[i]);
}
for(int i = 1; i <= n; i++)
printf("%d ", sz[find(i)]);
printf("\n");
}
return 0;
}
参考文章
https://www.acwing.com/activity/content/code/content/1295501/
https://www.acwing.com/activity/content/code/content/1295781/
https://www.acwing.com/activity/content/code/content/1295501/
