eBay笔试第二批 第一题AC，第二题73
笔试是25道选择题（50分）+2道编程题（50分）
第一次笔试的时候我在飞机上就没参加~~一共两批~~~发个帖子祝自己进面试吧~~~~
第一题 过河
输入要过河的人数n和船可以承载的重量W，接下来是每个人的重量，求最少需要几趟
测试用例是：
3 6
1
2
3
输出结果为2
代码：
#include<iostream>
#include<map>
#include<vector>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int n, W;
cin >> n >> W;
vector<int>w(n);
for (int i = 0;i < n;i++) cin >> w[i];
sort(w.begin(), w.end());
reverse(w.begin(), w.end());
int res = 0;
while (w.size() > 0)
{
int a = w[0];
w.erase(w.begin());
res++;
for (int i = 0;i < w.size();i++)
{
if (w[i] + a <= W)
{
w.erase(w.begin() + i);
break;
}
}
}
cout << res;
return 0;
} 第一行输入 考纲里 一共有N个知识点，最多能记住M个，接下来遇到的K的知识点
第二行就是K个知识点了
遇到一个不记得的知识点会自闭后再记住，如果能记住的已经满了会先忘掉一个再记住，求自闭次数最少多少（每次忘掉的知识点可以自己调整）
这题用操作系统里的最优页面置换算法 不过后面会超时，只过了73
测试用例是：
3 2 6
1 2 3 1 2 3
输出4
过程：
遇到1 记住1
遇到2 记住2
遇到3 忘2记3
遇到1
2 忘1记2
3
#include <deque>
#include <cstdio>
#include <algorithm>
#include<iostream>
using namespace std;
struct opt
{
int value;
int time;
};
const int maxn = 100000;
int a[maxn];
int main()
{
deque<opt> dq;
deque<opt >::iterator pos;
int numyk, numqueye = 0;
int n;
int m;
cin >> m >> numyk >>n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
{
int in;
in = a[i];
if (dq.size() < numyk)//存在多余页框
{
int flag = 0;
for (pos = dq.begin(); pos != dq.end(); pos++)
if ((*pos).value == in)//存在元素和它相同
{
flag = 1;
break;
} //存在该元素
if (!flag) //不存在此元素
{
numqueye++;
opt temp;
temp.value = in;
int f = 0;
for (int j = i + 1; j < n; j++)
if (a[j] == in)
{
f = 1;
temp.time = j - i;
break;
}
if (!f)
temp.time = n;
dq.push_back(temp);
}
}
else
{
int flag = 0;
for (pos = dq.begin(); pos != dq.end(); pos++)
if ((*pos).value == in)
{
flag = 1;
break;
} //存在该元素
if (!flag)
{
numqueye++;//缺页数+1
int m = dq.front().time;
//printf("m初始值为%d\n", m);
deque<opt >::iterator mp = dq.begin();
for (pos = dq.begin(); pos != dq.end(); pos++)
{
//printf("%d %d\n", (*pos).value, (*pos).time);
if ((*pos).time > m)
{
//printf("迭代");
mp = pos;//时间最大的元素的位置
m = (*pos).time;
}
}
opt temp;
temp.value = in;
int f = 0;
dq.erase(mp);
for (int j = i + 1; j < n; j++)
if (a[j] == in)
{
f = 1;
temp.time = j - i;
break;
}
if (!f)
temp.time = n;
dq.push_back(temp);
}
}
//每次之后重置
for (pos = dq.begin(); pos != dq.end(); pos++)
{
//printf("队列中的元素为 %d\n", (*pos).value);
int f = 0;
for (int j = i + 1; j < n; j++)
if (a[j] == (*pos).value)
{
f = 1;
(*pos).time = j - i;
break;
}
if (!f)
(*pos).time = n;
}
}
cout << numqueye;
} 