阿里后台内推(2020)

第一题:

样例:

Input:

9

1 2 3 4 5 6 7 100 200

Output:

303


解题思路:

中位数到个数的距离和最小,因此相对整个序列排序,然后再求中位数到其余个数的距离和。
#include<iostream>
#include<algorithm>
using namespace std; 
#define M 100000
int main()
{
    
    long long arr[M];//数比较大,所以所以使用long long 整型
    int N;
    cin>>N;
    for(int i =0;i < N;i++)
    {
    	cin>>arr[i];
	}
	sort(arr,arr+N);//对所有数排序 
	
	long long  total = 0;
    long long middle = arr[N/2] ;//中位数,数列中中位数到其余各个坐标的值最小 
	for(int i  = 0;i < N/2;i++ ) 
	{
		total += (arr[N-1-i] - arr[i]);//原式为middle - arr[i] + arr[N-1-i]- middle 
		
	}
	cout<<total<<endl;
    return 0;
}

试题二:




样例:

Input:

5 3

1 1 2 4

2 3

2 1

4 3

Output:

A

B

B

思路:
求小强和小明分别到根节点的高度,根据高度比较谁先胜。

Implemention:
#include<iostream>
using namespace std;
#define N 100000//最多10个节点
char playGame(int x,int y,int arr[],int n){
if(x==1) //小明开始就在根节点,则小明胜
return 'A';

if(y == 1)//小强开始就在根节点,则小强胜
return 'B';
//分别计算x和y到树根的路径长度
int hx = 0,hy = 0;
while(x!=0)//小强到根节点的高度
{
x= arr[x];
hx++;
}
while(y!=0)//小明到根节点的高度
{
y = arr[y];
hy++;
}
if (hx >= hy+1)//小强离根远 ,小明胜
{
return 'B';
}
else//小强离根远 ,小明胜
{
return 'A';
}
}
int main()
{
int n,m;
cin>>n;
cin>>m;
int arr[N] = {0};
int rounds[N][2];
for(int i  = 2;i <= n;i++ )
{
cin>>arr[i];
}
for(int i  = 0;i < m;i++ )
{
cin>>rounds[i][0];
cin>>rounds[i][1];
}

for(int i =0;i  < m;i++)
{
char res = playGame(rounds[i][0],rounds[i][1],arr,n);
cout<<res;
if(i < m-1)
cout<<" ";
}
return 0;
}





#笔经##阿里巴巴#
全部评论

相关推荐

2 2 评论
分享
牛客网
牛客企业服务