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数组的任意两个元素,求最小交换次数。

最新文章

  1. JSSDK用法//////////////////zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
  2. Unity学习笔记
  3. static关键字详解
  4. POJ2387 Til the Cows Come Home(SPFA + dijkstra + BallemFord 模板)
  5. 函数lock_rec_get_n_bits
  6. HDU 5744 Keep On Movin (贪心)
  7. WEB Application Development Integrator : 应用设置
  8. Android 使用动态载入框架DL进行插件化开发
  9. 在 Visual Studio 调试器中指定符号 (.pdb) 和源文件
  10. window7 安装sass和compass
  11. gym 101982 B题 Coprime Integers
  12. BZOJ2275[Coci2010]HRPA——斐波那契博弈
  13. Linux记录-监控系统开发
  14. kindeditor上传图片的大小在哪控制
  15. Hive配置永久显示表字段名并且不显示表名
  16. Delphi根据方法名调用方法
  17. 第十章&#160;优先级队列 (b4)完全二叉堆:批量建堆
  18. 2-2 R语言基础 向量
  19. java 实现生产者-消费者模式
  20. 火狐浏览器访问网站出现 HTTP Error 400. The request is badly formed.错误,怎么解决

热门文章

  1. webpack-Hot Module Replacement(热更新)
  2. SQL 通用数据类型
  3. #define中的#和##作用
  4. 配置pydot环境
  5. maven 项目 spring mvc + jdbc 配置文件
  6. Java数据类型的分类
  7. js闭包的本质
  8. iOS设备,fixed布局出问题
  9. Linux设备驱动--块设备(三)之程序设计
  10. 《CMake实践》笔记二:INSTALL/CMAKE_INSTALL_PREFIX【转】