字节跳动笔试题

字节跳动笔试题

昨天字节跳动笔试题目，没有ac一道，我很受打击。打算以后每笔试或面试一次，都仔细钻研，记录下自己的收获。也欢迎朋友们指出我写博客中的错误或给出更简单的方法。

1.田忌赛马问题

两个小组A、B，每个小组有n个同学。已知每位同学的速度。两个小组进行赛跑获取积分，每次派出一名同学，胜者+1，败者-1，平局+0。问A组最多积多少分。输入n代表n名同学，在输入n个数代表A组每人速度，又n个数代表B组每人速度。

输入样例： 3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0

输出样例： 1 0

0

这道题一开始搞错了策略，在这个题上花费了不少时间也才过了50多的用例。后来听说是田忌赛马问题，看了看其他人的博客后发现正解思路应该是这样：

先给两组数据排序。

（1）A组最快>B组最快：让他俩比赛，A组积分+1

（2）A组最快

（a）A组最慢>B组最慢：他俩比赛,积分+1 （b）其他情况：A组最慢与B最快比，

（b1）A最慢=B最快：他俩比，积分不变 （b2）A最慢

#include #include #include using namespace std; int main(){ int n;

cin>>n;//比赛数

vector a(n,0);//a组速度 vector b(n,0);//b组速度 for(int i=0;i>a[i]; }

for(int i=0;i>b[i]; }

sort(a.begin(),a.end());

sort(b.begin(),b.end());

int res = 0;

int ab = 0,bb = 0, ae = n-1, be = n-1; while( ae>=ab && be>=bb ){ if(a[ae]>a[be]){ // > res++; ae--; be--;

} else if(a[ae]b[bb]){ res++; ab++;

bb++; } else{

if(a[ab]