网易题目主要考察基础数据机构，都是模拟题，即按照题目操作选取对应的数据结构进行模拟操作即可。虽然博主很菜并不知道第三题的细节出了什么问题，第三题0都过不了，分享一下自己的思路。
第一题---乒乓球
每队6个人，3男3女，分别参加男双女双混双，所有人都要上，那么实际上每队只有9种出战策略。那么AB队各9种出战策略，直接枚举所有情况也就81种情况。直接写代码模拟就完事了，不想想花里胡哨的。
第二题---石头剪刀布
观察数据大小，最多1000个人，猜拳最多发生1000次。1000*1000=1e6左右，同样可以直接枚举算。
使用vec存每个人出什么(字符转成数字，好存，而且好判断输赢)，再使用vis标记是否出局，原数据顺时针输出，默认向右打就好了，模拟游戏向右打M次，比较从谁开始剩余次数多即可。
第三题---分数排序
个人觉得这题出的好好，非常有游戏的感觉，虽然死活过不了，与大家分享下我的思路，恳请大佬评论区说我错哪了，我查了快40分钟了估计。
首先思考题目的要求
- 要有一个分数列表，是顺序的
- 通过id要索引到旧的分数(对比是否有提升)
- 通过id要索引到是否拿过礼物(防止重复拿)
- 可以拿到分数的中位数
基于以上几点，考虑到堆的中位数不好拿，所以决定直接用deque存分数，然后手动维护分数列表的有序型。同时使用map以用户id作为key，value使用pair存分数以及是否拿过礼物。那么还有一个问题，怎样进行分数的更新。考虑到分数是不需要与用户一一绑定的，比如分数列表有10个2分，此时有一个曾经拿了2分的用户拿到了4分，我们并不需要找到他当初拿的那个2分删除，随便找个2分删就完事了。
整体模拟流程如下
输入一条数据
map找玩过没 没玩过
插入新数据 分数***deque
玩过
是否超过旧的分数,没超过直接退出当次循环
超过旧的分数
在deque找个与旧分数相等的分数删掉，插个新的分数 计算中位数 看是否与当前分数相等
检查领没领过礼物
map存 id： 分数 + 礼物拿过没
deque 只用存分数队列
需要重写deque的插入删除函数保证有序型，同时要用到二分查找快速定位分数索引。
2w条记录，数据量上可以直接做，直接做好维护即可。疑问点
分数与上一次玩相同但是突然符合中位数，拿不拿礼物？(都试过了，还是一个都过不了，菜了)
以下为代码:乱七八糟的注释较多，希望大家见谅。！第三题是不通过的代码，也顺手贴上来了希望有大佬指正！
三题的代码
//第一题
#include<iostream>
#include<vector>
using namespace std;
int main(){
int T ;
cin>>T;
for(int _i = 0 ; _i < T ; ++_i){
vector<int> teamAmale,teamAfe;
vector<int> teamBmale,teamBfe;
int pow;
for(int _t = 0 ; _t < 3; ++_t){
cin>>pow;
teamAmale.push_back(pow);
}
for(int _t = 0 ; _t < 3; ++_t){
cin>>pow;
teamAfe.push_back(pow);
}
for(int _t = 0 ; _t < 3; ++_t){
cin>>pow;
teamBmale.push_back(pow);
}
for(int _t = 0 ; _t < 3; ++_t){
cin>>pow;
teamBfe.push_back(pow);
}
//输入完毕
//实际上每对9种组队方法， 剩下的选人就确定下来了 一共81局
//甚至可以直接遍历
int Bwintimes;
vector<vector<int> > Ascore(9,vector<int>(3));
vector<vector<int> > Bscore(9,vector<int>(3));
//算出A和B所有组合的得分情况。
//男 女 混
int Anan , Anv , Ahun;
int Bnan , Bnv , Bhun;
int idx = 0;
for(int i = 0 ; i < 3; ++i){
for(int j = 0 ; j < 3 ; ++j){
Anan = teamAmale[0]+teamAmale[1]+teamAmale[2]-teamAmale[i];
Anv = teamAfe[0]+teamAfe[1]+teamAfe[2]-teamAfe[j];
Ahun = teamAmale[i]+teamAfe[j];
Ascore[idx][0] = Anan;
Ascore[idx][1] = Anv;
Ascore[idx][2] = Ahun;
Bnan = teamBmale[0]+teamBmale[1]+teamBmale[2]-teamBmale[i];
Bnv = teamBfe[0]+teamBfe[1]+teamBfe[2]-teamBfe[j];
Bhun = teamBmale[i]+teamBfe[j];
Bscore[idx][0] = Bnan;
Bscore[idx][1] = Bnv;
Bscore[idx][2] = Bhun;
idx++;
}
}
//比较81次即可
int ans=0;
int Bwin=0;
for(int i = 0 ; i < 9 ; ++i){
for(int j = 0 ; j < 9 ;++j){
Bwin = 0;
if(Ascore[i][0] < Bscore[j][0]) Bwin++;
if(Ascore[i][1] < Bscore[j][1]) Bwin++;
if(Ascore[i][2] < Bscore[j][2]) Bwin++;
if(Bwin>=2) ans++;
}
}
cout<<ans<<endl;
}
return 0;
} //第二题
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
vector<int> vec;
int beat(int i , int j ){
if(vec[i] == vec[j]) return 0;
if(abs(vec[i] - vec[j])==1){
if(vec[i] > vec[j]) return 1;
else return -1;
}
//只剩下02的情况的
if(vec[i] > vec[j]) return -1;//2 0 输了
else if(vec[i] < vec[j]) return 1;//0 2 赢了
return -999;
}
int main(){
int T ;
cin>>T;
for(int _i = 0 ; _i < T ; ++_i){
int N ,M;//N人数 M轮次
cin>>N>>M;
vec.clear();
//用数字代表石头剪刀布
//2 1 0；
char chos;
for(int _t= 0 ; _t < N ; _t++){
cin>>chos;
if(chos=='R')vec.push_back(2);
else if(chos == 'S') vec.push_back(1);
else if(chos == 'C') vec.push_back(0);
}
//能否模拟，用什么模拟
//1000个人 最多打1000次 可以模拟 1000*1000 = 1e6；
int maxrest = -1;
for(int i = 0 ; i < N ; i++){
//从第i个人开始打，向右打
int cur = i;//当前的人
int rcur = (i+1)%N;
int rest = N;//剩余的人
vector<int> vis(N);//标记存活状态
int flag;
for(int t = 0 ; t < M ; ++t){
//M轮次
flag = beat(cur,rcur);
if(flag > 0){
//cur赢了 右侧人移动
vis[rcur] = 1;
while(vis[rcur] == 1){
rcur = (rcur+1 )%N;
}
rest--;
}
else if(flag == 0){
//平局
cur = rcur;
rcur = (rcur+1)%N;//右移动
while(vis[rcur] == 1){
rcur = (rcur+1 )%N;
}
}
else if(flag < 0){
//cur输了
vis[cur] = 1;
cur = rcur;
rest--;
rcur = (rcur+1) % N;
while(vis[rcur] == 1){
rcur = (rcur+1 )%N;
}
}
}
maxrest = max(maxrest,rest);
}
cout<<maxrest<<endl;
}
return 0;
} //第三题，过不了过不了过不了
#include <iostream>
#include <vector>
#include <deque>
#include <map>
using namespace std;
//deq排序从小到大
int find(int score , deque<int>& deq){
//返回deq中012456 搜3 返回3 搜7返回6？ 第一个大于等于score的索引
int l = 0 ;
int r = deq.size()-1;
int mid;
while(l<=r){
mid = (l+r)/2;
if(deq[mid] == score){
r = mid-1;
}
else if(deq[mid] < score){
l = mid+1;
}
else if(deq[mid] > score){
r = mid-1;
}
}
return r+1;
}
void ins(int score , deque<int>& deq){
//往deq插入一个数，并且维护好顺序
if(deq.size() == 0){
deq.push_back(score);
return;
}
int num = find(score , deq);//返回的是第一个大于或者等于的 插在这个之前 没毛病
deq.insert(deq.begin()+num, score);
return ;
}
double getmid(deque<int>& deq){
int n = deq.size();
if(n%2 == 0){
//偶数
return (0.0+deq[n/2] + deq[n/2-1])/2;
}
else
return deq[n/2];
}
int main(){
int T;
cin>>T;
for(int _i = 0 ; _i < T ; ++_i){
int N;
cin >> N;
//输入一条数据
//map找玩过没 没玩过插入新数据 分数***deque
//map玩过 看看超没超过旧的 超过旧的去deque找个旧的 删掉，插个新的分数
//计算中位数 看相不相等 检查领没领过礼物
//关注点 同分但是突然符合中位数 也要拿礼物？
//map存 id： 分数 + 礼物拿过没
//deque 只用存分数队列
//2w条记录，好像可以直接冲，直接做好维护即可。
map<int,pair<int,int> > memo;//玩家号 分数 领过礼物否
deque<int> deq;//分数队列
int id,score;
double midscore;//中位数
int times=0;//领礼物次数
int oldscore;
for(int _t =0 ; _t < N ; ++_t ){
cin>>id>>score;
if(memo.count(id) == 0){
memo[id] = make_pair(score,0);//0是没拿过礼物
ins(score,deq);
}
else{//memo已有数据
oldscore = memo[id].first;
if(score >= oldscore){
//超过旧的 要去更新下分数
int pos = find(oldscore,deq);
//直接删除这个迭代器 再插
deq.erase(deq.begin()+pos);
ins(score,deq);
}
else{
continue;//没有触发分数更新 是不领奖的
}
}
midscore = getmid(deq);//找中间分数
if(midscore==score && memo[id].second == 0){
memo[id].second=1;
times++;
}
}
cout<<times<<endl;
}
return 0;
} 
全部评论
(3) 回帖