1 题目描述

郭老师爱猜果子

郭老师家有个果园，每年到了秋收的时候都会收获很多不同种类的果子。郭老师有个癖好，就是每年收完果子后，想从中选出最大和最小的果子。

郭老师每次可以比较2个果子的相对大小，但不知道果子的具体大小，即果子的大小用数字表示的话，可以用负数表示，但是相对大小不变，果子的编号也不变，比较方式如下：

int cmp(int i, int j)函数

这次郭老师有事需要外出，找到了你帮他找出最大和最小的果子。但是你只能使用上述比较方式找出最大和最小的果子。而且这种比较方法比较费力，所以你需要尽可能少的调用cmp来解决此问题。

输入描述

输入包括两行

第一行是一个整数 n （1 ≤ n ≤ 100000），表示果子共有2n个。

第二行包含2n个int整数。

输出描述

你需要在findminandmax函数里输出最小和最大果子的编号（从1开始），以空格隔开。如果有多个最小值或最大值，输出任意一个即可。

接下来将由系统输出你的询问记录。

当你的答案正确且你询问的次数为小于3n时，你将AC此题。

预设代码

前置代码

#include
using namespace std;
const int maxn = 200005;
int n;
int a[maxn];
void findminandmax(int n); // you should finish this
int cmp(int i, int j)
{
if (i <= 0 || i > 2 * n || j <= 0 || j > 2 * n) return -2;
if (a[i] > a[j]) return 1;
if (a[i] == a[j]) return 0;
if (a[i] < a[j]) return -1;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= 2 * n; i++)
scanf("%d", &a[i]);
findminandmax(n);
return 0;
}
/*
void findminandmax(int n)
{
// finish this
}
*/

/* PRESET CODE END - NEVER TOUCH CODE ABOVE */

2 代码

#include   
using namespace std;  
const int maxn = 200005;  
int n;  
int a[maxn];  
void findminandmax(int n); // you should finish this  
int cmp(int i, int j)  
{  if (i <= 0 || i > 2 * n || j <= 0 || j > 2 * n) return -2;  if (a[i] > a[j]) return 1;  if (a[i] == a[j]) return 0;  if (a[i] < a[j]) return -1;}  
int main()  
{   //freopen("file in.txt","r",stdin);scanf("%d", &n);  for (int i = 1; i <= 2 * n; i++)  scanf("%d", &a[i]);findminandmax(n);  return 0;  
}  
/*
这个方法的平均复杂度是3n-3<3n,但是题目要求的是每一次都要低于3n，所以只能过掉其中一部分用例
平均复杂度是考虑最坏和最好的两种情况的复杂度直接加起来除以2得到
void findminandmax(int n) 
{ long long  i; //作为下标遍历数组long long  min,max;  int cmpresult;cmpresult = cmp(1,2);if(cmpresult==1){min = 2;max = 1;}if(cmpresult==0){min=max=2;}if(cmpresult==-1){min = 1;max = 2;}//从第三个果子开始比较i=3;while(i<=2*n){cmpresult = cmp(min,i);if(cmpresult==1){   //如果比之前的最小的还小，更换min=i;}        if(cmpresult==-1){  //如果比最小的大，则和之前最大的进行比较cmpresult = cmp(max,i);if(cmpresult==-1){max=i;}}i++;}cout<long long i;long long min,max;int ans1,ans2,ans3;ans1 = cmp(1,2);if(ans1==1){min = 2;max = 1;}if(ans1==0){min=max=2;}if(ans1==-1){min = 1;max = 2;}i=3;while(i<2*n){ans1 = cmp(i,i+1);if(ans1==-1){ //i比较小，i+1比较大ans2 =cmp(min,i);  //min和i进行比较if(ans2==1){ //i比较小min=i;}ans3 = cmp(max,i+1);if(ans3==-1){   //i+1比较大max=i+1;}}if(ans1==1){    //i比较大,i+1比较小ans2=cmp(min,i+1);if(ans2==1){min=i+1;}ans3=cmp(max,i);if(ans3==-1){max=i;}}i += 2;  //一次直接取出来两个，所以+2}cout<