阿里后台内推(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;
}
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;
}
社会上还是不能想的太简单