列表

详情

NC25109. 小w的矩阵前k大元素

描述

小w现在有两个长度为n的数组a[ ]和长度为m的数组b[ ]，现在小w用它们两个构造了一个二维数组c[ ][ ]。

c中的每个元素c[i][j]被定义为c[i][j]=a[i]+b[j]。其中i表示行，j表示列，数组的下标均从0开始计算。

现在小w把这个数组画到了一张纸上面。例如当a[ ]={1,2,3,4,5,7}，b[ ]={1,2,3,4,5}时。画在纸上的数组如图所示

现在小w在这个数组(0,0)的位置放置了一个棋子。小w准备进行q次操作。

1、将棋子向右移动dy步，如果移动dy步之后越出了棋盘，只需将棋子移动到棋盘的最边缘即可。即(x,y)->(x,min(m-1,y+dy))。

2、将棋子向下移动dx步，如果移动dx步之后越出了棋盘，只需将棋子移动到棋盘的最边缘即可。即(x,y)->(min(n-1,x+dx),y)。

3、查询从(0,0)到(x,y)的这个子矩形中，升序排列的前k个元素是什么，请你输出升序k个整数。输入数据保证k不多于当前子矩形中的元素个数，同时保证所有查询k的总和不多于。

输入描述

第一行输入三个整数n,m,q,，分别表示a数组的长度，b数组的长度，操作的总次数。
接下来一行n个整数a[i]表示a数组的第i个元素。
接下来一行m个整数b[i]表示b数组的第i个元素。

接下来q行，每行一个字符及一个操作参数。

当输入的字符为'R'时，表示棋子向右移动，输入的参数dy表示向右移动的步数。
当输入的字符为'D'时，表示棋子向下移动，输入的参数dx表示向下移动的步数。
当输入的字符为'Q'时，查询从(0,0)到(x,y)的这个子矩形中，升序排列的前k个元素是什么，请你升序输出k个整数。输入数据保证k不多于当前子矩形中的元素个数，同时保证所有查询k的总和不多于。
输入数据保证至少进行了1次查询操作。

输出描述

对于每个Q，按照升序顺序输出k个整数。输出的整数之间用空格隔开，行末不允许有多余空格。

示例1

输入: 

6 5 10
1 2 3 4 5 7
1 2 3 4 5
Q 1
R 1
D 1
Q 4
R 1
D 1
Q 7
R 100
D 100
Q 30

输出: 

2
2 3 3 4
2 3 3 4 4 4 5
2 3 3 4 4 4 5 5 5 5 6 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 10 10 11 12

说明:

第一次查询时，棋子在(0,0)，子矩阵升序排列的前1个是2
第二次查询时，棋子在(1,1)，子矩阵升序排列的前4个是2,3,3,4
第三次查询时，棋子在(2,2)，子矩阵升序排列的前7个是2,3,3,4,4,4,5
第四次查询时，棋子在(5,4)，子矩阵升序排列的前30个是2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,10,10,11,12

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 168ms, 内存消耗: 11620K, 提交时间: 2019-07-03 17:17:23 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
struct node
{
	multiset<int>::iterator a,b;
	bool operator <(const node &o)const{
		return (*o.a)+(*o.b)<(*a)+(*b);
	}
};
multiset<int> aa,bb;
int main(){
	int n,m,q;
	int l=1,r=1;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=m;++i) scanf("%d",&b[i]);
	aa.insert(a[1]);
	bb.insert(b[1]);
	while(q--){
		char s[5];
		int k;
		scanf("%s%d",s,&k);
		if(s[0]=='Q'){
			priority_queue<node>que;
			node x;
			x.a=aa.begin();
			x.b=bb.begin();
			que.push(x);
			while(k--){
				node tp=que.top();que.pop();
				printf("%d ",(*tp.a)+(*tp.b));
				node x=tp;
				if(x.a==aa.begin()){
					x.b++;
					if(x.b!=bb.end()){
						que.push(x);
					}
					
				}
				tp.a++;
				if(tp.a!=aa.end()){	
					que.push(tp);
				}
			}
			puts("");
		}
		else if(s[0]=='R') {
			int i=r+1;
			r=min(m,r+k);
			for(;i<=r;++i ) bb.insert(b[i]);
		}
		else{
			int i=l+1;
			l=min(n,l+k);
			for(;i<=l;i++) aa.insert(a[i]);
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 301ms, 内存消耗: 13044K, 提交时间: 2019-11-06 20:12:22 

#include<stdio.h>
#include<set>
#include<queue>
using namespace std;const int MAXN =1e5 + 50;int r[MAXN], c[MAXN],v[MAXN];multiset<int>::iterator cur[MAXN],it;struct S{int v,id;bool operator<(const S& R)const{return v>R.v;}};int main(){int n,m,q,k=1,j=1,x,i;scanf("%d%d%d",&n,&m,&q);for(i=1;i<=n;i++)scanf("%d",r+i);for(i=1;i<=m;i++)scanf("%d",c+i);multiset<int>y,g;y.insert(r[1]);g.insert(c[1]);for (int e=1;e<=q;e++){char op[3];scanf("%s%d",op,&x);if (op[0]=='R'){int newc=min(m,j+x);while(j<newc)g.insert(c[++j]);}else if(op[0]=='D'){int newr=min(n,k+x);while (k<newr)y.insert(r[++k]);}else{priority_queue<S>pq;it=y.begin();for (int i=1;i<=x&&it!=y.end();i++){cur[i]=g.begin();pq.push({*it+*cur[i],i});v[i] =*it++;}while(x){S tmp=pq.top();pq.pop();printf("%d%c",tmp.v,--x?' ':'\n');if(++cur[tmp.id]!= g.end())pq.push({*cur[tmp.id]+v[tmp.id],tmp.id});}}}}

上一题

© 2024 nowcoder.com