P8088 『JROI-5』Autumn

题目背景

感谢 @王熙文 提供了一种优于标算的做法。

题目描述

本题读入量较大，建议使用较快的读入方式，可以参考 赛时公告板

给定 $n$ 个数列，每个数列有 $m$ 个元素，第 $i$ 个数列第 $j$ 个元素为正整数 $a_{i,j}$。

你每次可以选择 $i_1,j_1$ 和 $i_2,j_2$，交换 $a_{i_1,j_1}$ 和 $a_{i_2,j_2}$。你至多可以进行 $x$ 次交换。

定义 $d_i$ 为第 $i$ 个数列中第 $k$ 大的元素。

请最小化 max ⁡ i = 1 n { d i } \max\limits_{i=1}^n \{d_i\} i=1maxn​{di​}。（表示 $d_1,d_2,\cdots ,d_n$ 中的最大值）

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行每行 $m$ 个正整数，表示数列。

最后一行两个正整数 $k,x$。

输出格式

一行一个数，输出最小化的 max ⁡ i = 1 n { d i } \max\limits_{i=1}^n \{d_i\} i=1maxn​{di​}。

输入输出样例 #1

输入 #1

5 5
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 1

输出 #1

8

输入输出样例 #2

输入 #2

5 5
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 2

输出 #2

7

输入输出样例 #3

输入 #3

见附件

输出 #3

见附件

说明/提示

对于样例 1，将 $a_{2,5}$ 和 $a_{1,5}$ 交换，可以证明，没有更优策略。

---

对于 $30\%$ 的数据，$x=10^6,1\le k\le m$。

对于另外 $10\%$ 的数据，所有的数都相等。

对于另外 $30\%$ 的数据，$1\le n,m\le 2\times 10^3,1\le k\le m,a_{i,j}\le 10^6,0\le x\le n\times m$。

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^3,1\le k\le m,1\le a_{i,j}\le 10^{18},0\le x\le n\times m$。

C++实现

#include<bits/stdc++.h>
#define int long long
const int N=2e3+3;
bool cmp(int a,int b)	{return a>b;}
int n,m,k,x,a[N][N];
std::priority_queue<int,std::vector<int>,std::greater<int> >S;
std::priority_queue<int,std::vector<int>,std::less<int> >T;
signed main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);std::cout.tie(0);
	std::cin>>n>>m;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			std::cin>>a[i][j];
		}
		std::sort(a[i]+1,a[i]+m+1,cmp);
	}
	std::cin>>k>>x;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			if(j<k)	S.push(a[i][j]);
			else T.push(a[i][j]);
		}
	}
	while(x) {
		if(S.top()<T.top()) {
			int a1=S.top(),a2=T.top();
			S.pop();T.pop();
			S.push(a2);T.push(a1);
			x--;
		}
		else break;
	}
	std::cout<<T.top();
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容