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

1809: make pair

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 60 Solved: 44

Submit Status Web Board

Description

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

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

问题是这样的，在构造出了n²个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;

}

巴特西