拼多多算法岗第4题

	#include<stdio.h>

#include<string.h>

#include<algorithm>
using namespace std;



	void sort_up(int a[], int n);

void sort_down(int a[], int n);

int cmp(int a, int b);

int  deleted(int flag, int a[], int n, int b[], int cn);



	int main()

{

int n = 0;

int a[50];

int b[50];

long long cnt = 0;

int num = 0;

int rest = 0;

int  cn = 0;

int sortflag = 0;

scanf_s("%d", &n);

for (int i = 0; i < n; i++)

{

scanf_s("%d", &a[i]);

b[i] = a[i];

}

num = n;

cn = n;

sort_up(a, n);

for (int i = 0; i < n; i++)

{

if (b[0] != b[1])

{

if (b[i] == a[i] || b[i] == a[n - i])

sortflag++;

}

else

break;

}

if (sortflag == n)

{

cnt = 1;

printf("%lld", cnt);

return 0;

}

sortflag = 0;

for (int i = 0; i < n; i++)

{

if (b[0] == a[i])

sortflag++;

}

if (sortflag == n)

{

cnt = n;

printf("%lld", cnt);

return 0;

}



for (int j = 0; j < n; j++)

{

if (b[j] == 0)

continue;

memcpy(a, a, num*sizeof(int));

memset(a + num, 0, (cn - num)*sizeof(int));

rest=deleted(b[j], a, num,b,cn);

num = rest;

//rest = cn - num;



	cnt++;

if (rest == 0)

break;

}

printf("%lld", cnt);

return 0;

}

int  deleted(int flag, int a[], int n,int b[],int cn)

{

int k=0;

int i=0;

sort_up(a, n);//升序

if (flag >=a[n / 2])

{

//采取降序规则

for (i = 0,k=0; i < cn;i++)

{

if (b[i] <= flag)

b[i] = 0;

if (b[i] != 0)

a[k++] = b[i];

}

}

else

{

//采取升序规则

for (i = 0, k = 0; i < cn; i++)

{

if (b[i] <= flag)

b[i] = 0;

if (b[i] != 0)

a[k++] = b[i];

}

}

return k;

}



	//升序

void sort_up(int a[], int n)

{

sort(a, a + n);

}

//降序

void sort_down(int a[], int n)

{

sort(a, a + n, cmp);

}

int cmp(int a, int b)

{

return a > b;

}