zzulioj--1089--make pair(dfs+模拟)

1809: make pair

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 60  Solved: 44



SubmitStatusWeb Board

Description

pair<T,T>是c++标准模板库中一种十分有用的模板类型,它是一个二元组。我们可以用它来表示一个二维坐标点,人的身高体重等等。make_pair()函数可以方便地构造一个pair。

现在有一个长度为n的整数数组a1~an(可以存在相同的元素),将每两个元素(包括自身)make_pair(),一定能得到n2个pair。例如,[1,2,3]make_pair()后,将得到{[1,1],[1,2],[1,3], [2,1],[2,2],[2,3], [3,1],[3,2],[3,3]}。

问题是这样的,在构造出了n2个pair后,升序排序(先按第一维排序,若第一维相等,再按第二维排序),你能找到排序后的第k个元素吗?

Input

多组数据。

第一行,2个整数n和k (1<=n<=10000,1<=k<=n^2)。

第二行,n个整数,即原数组a1~an(1<=ai<=1000000000)。

Output

对于每组数据,输出两个整数,排序后的第k个pair。

Sample Input

2 4

2 1

3 2

3 1 5

Sample Output

2 2

1 3

一般的组合数问题,不一样的地方就是输出第几个组合数,将k设置为全局变量,找到一个就k--,到k==0时输出

#include<stdio.h>
#include<string.h>
#define MAX 100010
#include<algorithm>
using namespace std;
int num[MAX],a[MAX];
int n,k;
void dfs(int p)
{
if(p>2)
return ;
for(int i=0;i<n;i++)
{
a[p]=num[i];
if(p==2)
{
k--;
if(!k)
{
printf("%d %d\n",a[1],a[2]);
return ;
}
}
dfs(p+1);
}
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d",&num[i]);
sort(num,num+n);
dfs(1);
}
return 0;
}

这是一个模拟的代码,可以自己列几组数据

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int num[10010];
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
sort(num+1,num+n+1);
int x,y;
if(k%n)
{
x=k/n+1;
y=k%n;
}
else
{
x=k/n;
y=n;
}
printf("%d %d\n",num[x],num[y]);
}
return 0;
}
上一篇:UVALive - 6436、HYSBZ - 2435 (dfs)


下一篇:牛客~~扫雷~~~DFS+模拟