阿里后台内推(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;
}