L 裁纸片 贪心 + 模拟
2024-08-26 21:27:19
https://biancheng.love/contest-ng/index.html#/123/problems
如果只是输出最小的值,那么好办,a升序,b降序,这样是最优的。
但是需要次数,这就麻烦了。
但是注意到它说数字互不相同。
那么,用个数组book[a[i]]表示a[i]需要匹配的是那个数字,就是a数组的最小值,需要匹配b数组的最大值。
然后从原数组中模拟。
因为可能并不需要全部都排序的,本来就一一对应的话,就不需要排。
比如
2 1
1 2
也是不需要排的。
然后就是模拟了,对于如果不是一一对应的每一个数,就去找一个和它对应的,交换就行了。只有这样的解了。
1
3
1 2 3
2 1 3
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 3e6 + ;
LL a[maxn];
LL b[maxn];
LL tocmpa[maxn];
LL tocmpb[maxn];
int book[maxn];
int pos[maxn];
const int fix = 1e6;
void work() {
int n;
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%lld", &a[i]);
tocmpa[i] = a[i] + fix;
}
for (int i = ; i <= n; ++i) {
scanf("%lld", &b[i]);
tocmpb[i] = b[i] + fix;
pos[tocmpb[i]] = i;
}
sort(a + , a + + n);
sort(b + , b + + n, greater<LL>());
LL ans = ;
for (int i = ; i <= n; ++i) {
ans += a[i] * b[i];
}
for (int i = ; i <= n; ++i) {
book[a[i] + fix] = b[i] + fix;
}
int anstime = ;
// for (int i = 1; i <= n; ++i) {
// printf("%d ", pos[book[tocmpa[i]]]);
// }
// printf("\n");
for (int i = ; i <= n; ++i) {
if (book[tocmpa[i]] == tocmpb[i]) continue;
anstime++;
int wan = book[tocmpa[i]];
int cur = tocmpb[i];
int poswan = pos[wan];
int poscur = pos[cur];
swap(tocmpb[poswan], tocmpb[poscur]);
swap(pos[wan], pos[cur]);
}
printf("%lld %d\n", ans, anstime);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
这题的原题其实是:
给定两个数组,要使得b数组变成a数组,每次可以交换b数组的任意两个元素,求最小交换次数。
最新文章
- JSSDK用法//////////////////zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
- Unity学习笔记
- static关键字详解
- POJ2387 Til the Cows Come Home(SPFA + dijkstra + BallemFord 模板)
- 函数lock_rec_get_n_bits
- HDU 5744 Keep On Movin (贪心)
- WEB Application Development Integrator : 应用设置
- Android 使用动态载入框架DL进行插件化开发
- 在 Visual Studio 调试器中指定符号 (.pdb) 和源文件
- window7 安装sass和compass
- gym 101982 B题 Coprime Integers
- BZOJ2275[Coci2010]HRPA——斐波那契博弈
- Linux记录-监控系统开发
- kindeditor上传图片的大小在哪控制
- Hive配置永久显示表字段名并且不显示表名
- Delphi根据方法名调用方法
- 第十章&#160;优先级队列 (b4)完全二叉堆:批量建堆
- 2-2 R语言基础 向量
- java 实现生产者-消费者模式
- 火狐浏览器访问网站出现 HTTP Error 400. The request is badly formed.错误,怎么解决