2017年暑期实习生招聘（百度）——两道编程题

1）度度想去商场买一顶帽子，商场有N顶帽子，有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子，问第三便宜的帽子价格是多少？

输入描述：首先输入一个正整数N,(N <= 50),接下来输入N个人数表示每顶帽子的价格(价格均是正整数，且小于等于1000)

输出描述：如果存在第三便宜的帽子，请输出这个价格是多少，否则输出-1

输入例子： 10 10 10 10 10 20 20 30 30 40 40

输出例子：

30

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

我的思路是：（桶排序 + 暴力大法）

#include<vector>
#include<iostream>
using namespace std;

#define BigPrice 1000

void SortPrice(int price[],int len,int &three)
{
 if(price == NULL || len<= 0)
  return;//--------------------判断边界条件
 
 int NewPrice[BigPrice+1] = {0};
 for(int i=0;i<len;++i)
 {
  int prices = price[i];
  if(prices < 0 || prices > BigPrice)
   continue;
  ++NewPrice[prices];
 }
 int index = 0;
 for(int j=0;j<BigPrice;++j)
 {
  if(NewPrice[j]!=0)
  {
   ++index;
  }
  if(index == 3)
  {
   three = j;
   break;
  }
  else 
  {
   three = -1;
  }
 }
}

完了之后问了下大神，人家用是三个数轮回记录。还有个大大神用的好像是位运算....................................

3)不等式数列度度熊最近对全排列特别感兴趣，对于1到n的一个排列，度度熊发现可以在中间根据大小关系插入合适的大小和小于符号(即'>'和'<')使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即('<'),和n-k-1个大于符号(即'>'),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其成为合法的不等式数列。

例如n = 3,k = 1; 1到3的排列中，可以插入1个小于符号

形成的不等式数列有:

1<3>2 2<3>1 2>1<3 3>1<2

即132 231 213 312这4种排列是可以成为合法的不等式数列,所以答案是4

输入描述：输入包括一行，包含两个整数n和k(k < n <= 1000)

输出描述：输出满足条件的排列数，答案对2017取模

输入例子： 5 2

输出例子： 66

---------------------------------------------------------------------------------------------------------------------------------------------------------

难过，我还是用的暴力。。。。。。。。。。。。

#include<vector>
#include<iostream>
using namespace std;

void shaixuan(int small_k,int big,int n);

int rem[1000];
int count = 0;

void swap(int &a,int&b)
{
 int temp;
 temp = a;
 a = b;
 b = temp;
}
void perm(int list[],int k,int m,int small_k,int big,int n)
{
 if(k == m)
 {
  for(int i=0;i<=m;i++)
  {
   rem[i] = list[i];
  }
  shaixuan(small_k,big,n);
 }
 else
 {
  for(int i = k;i<=m;i++)
  {
   swap(list[k],list[i]);//交换
   perm(list,k+1,m,small_k,big,n); 
   swap(list[k],list[i]);//恢复原样
  }
 }
}
void shaixuan(int small_k,int big,int n)
{
 int k = small_k;
 int b = big;
 int geshu = 0;
 for(int i=0;i<n-1;++i)
 {
  if(rem[i]<rem[i+1])
  {
   if(k>0)
   {
    --k;
    ++geshu;
   }
  }
  else if(rem[i]>rem[i+1])
  {
   if(b>0)
   {
    --b;
    ++geshu;
   }
  }

  if(geshu == n-1)
  {
   ++count;
  }
 }
 count = count%2017;
}

int main()
{
 int n;
 cin>>n;
 int small_k;
 cin>>small_k;
 int big = n - small_k - 1;
 int *list = new int[n];
 for(int i=0;i<n;++i)
 {
  list[i] = i+1;
 }
 perm(list,0,n-1,small_k,big,n);
 cout<<count<<endl;
 return 0;
}