20200801猿辅导笔试记录
- 重复的课程
- 发奖品
最近比较忙，没太多时间，所以题目写的略微粗略一些。
重复的课程
输入N表示N节课，接下来输入N行每行输入课程的开始时间和结束时间，求最多的时候有几节课时间重了。
输入示例 ：
4
1 4
1 2
2 3
3 4
输出：2
这个题目描述的就很神奇，题目竟然问的是最少？这里就不纠结题目，仅供讨论。
考虑一个时间段同时有几节课在上，在所有开始和结束的时间中遍历，如果开始一节课则同时上的课数目+1，结束一节课，则同时上的课数目-1。完整通过的人好像都是都是使用优先级队列，我觉得优先级队列在这里没必要。只需要记录一个数目即可。
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> start(n);
vector<int> end(n);
int a, b;
for(int i=0;i<n;i++)
{
cin >>a>>b;
start[i] = a;
end[i] = b;
}
sort(start.begin(),start.end());
sort(end.begin(),end.end());
int i=0, j=0, k=0, res=0;
while(i<n)
{
if (start[i]<end[j])
{
// 说明该在start[i]这个时段有课开了
k += 1;
i +=1;
res = max(k, res);
}
else
{
j+=1;
k-=1;
}
}
cout << res << endl;
return 0;
}
这是我的思路，但是可能会存在瑕疵，这里把我同学AC100的代码贴上来。使用的是优先级队列，但是思想还是一样的，区别在于用变量记录窗口内课程数目还是使用优先级队列。
#include <iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int n;
cin >> n;
vector<pair<int,int>>range(n);
for(int i=0;i<n;i++)
{
int a, b;
cin >> a >> b;
range[i].first = a;
range[i].second = b;
}
if (n == 1)
return 1;
if (n == 0)
return 0;
sort(range.begin(),range.end());
priority_queue<int,vector<int>,greater<int>>q;
q.push(range[0].second);
int ans = 1;
for (int i = 1; i < n; i++)
{
while (q.top() <= range[i].first)
q.pop();
q.push(range[i].second);
ans = max(ans, (int)q.size());
}
cout << ans << endl;
return 0;
}
考试的时候，我使用的是python，当时是比较原生，没有优化的代码。直接把start和end放在一个序列中，然后排序，判断窗口的课程数目，放在一个序列的时候依靠另一个标志来记录是开始还是结束。代码如下。
n = int(input())
res = []
for i in range(n):
s, e =[int(i) for i in input().split(' ')]
res.append([s, -1])
res.append([e, s])
res.sort(key=lambda x:x[0])
maxk = k = 0
for i in res:
if i[1]==-1:
k+=1
else:
k -=1
maxk = max(k, maxk)
print(maxk)
我写的两个代码的理论复杂度是一致的，无非就是python代码比较原生一些。但是这个代码，只过了55%的case。自己没找到原因，如果有人知道，或者指出我方法的问题，感激不尽。
发奖品
题目大意是这样，有个人拿到一堆奖券，但是自己只能持有一张，他需要把剩下的分给别人，每个拿到奖券的人也只能持有一张，需要继续分给别人。最后分完之后开奖，奖券对应一个奖励（会有负收益），最后需要计算每个人开奖的得分。
得分的计算需要保证，每个人只能计算自己的奖券(必须要算)，以及从自己这里分出去的奖券的收益（可以选择部分）。如果要计算间接从自己这里分出去的收益，则经由中间转手送出去的收益都要被计算。举个例子就是A分出去B，B分出去了C和D，如果A要计算C或D的收益，则必须要计算中间收益B。
输入示例：
3
2 0
1 2
-1 2
输入说明：第一行表示有n张奖券，第二行到第n+1行的两个数，表示这个人的奖券收益，和奖券来源。奖券来源i表明这个人的奖券来自于第i行的这个人。0表示他是奖券的源头。如2表示奖券来源于输入第二行这个人。
输出示例： 3
我已经把题目给大家理的很顺了。接下来就是上代码了。我一开始也看错了题目，题目要求所有人中最大的开奖得分。我以为只求第一个人的。然后一直通过0%。
最后两分钟发现了问题，改出来如下两版代码。
我的思想是递归，为每个奖券从这个奖券这里出去的，记为这个奖券的孩子。然后计算收益的时候，从上往下计算，如果孩子只有一张奖券，没有分出去的奖券，则看这个收益是否大于0，如果大于0则选，反之不选。如果孩子也有孩子，则递归计算孩子的收益。
第一般代码如下：
from collections import defaultdict
n = int(input())
res = []
send = defaultdict(list)
for i in range(n):
a, b = [int(i) for i in input().split(' ')]
res.append(a)
b -= 2
send[b].append(i)
def getMaxValue(k):
r = res[k]
if k in send:
for i in send[k]:
r += getMaxValue(i)
return max(r, 0) % 1000000003
a = 0
for i in range(n):
a = max(getMaxValue(i), a)
print(a)
提交后，过了50%的case，接着就回到这个老生常谈的话题，递归重复计算的问题。（注：如果只计算第一个发奖券的人，则不会有重复计算。）提交后还有一分钟，这个时候最快的方法就是加备忘录。
第二版加了备忘录，代码如下。
from collections import defaultdict
n = int(input())
res = []
send = defaultdict(list)
for i in range(n):
a, b = [int(i) for i in input().split(' ')]
res.append(a)
b -= 2
send[b].append(i)
me = {}
def getMaxValue(k):
if k in me:
return me[k]
r = res[k]
if k in send:
for i in send[k]:
r += getMaxValue(i)
me[k] = max(r, 0) % 1000000003
return me[k]
a = 0
for i in range(n):
a = max(getMaxValue(i), a)
print(a)
本以为第一版是超时，然后提交了第二版，以为没问题了，结果令我大吃一惊，发现AC还是50%。然后时间到了。我猜测这里可能是因为如果所有的中奖收益都是负数，我的代码返回的不是最大的收益，而是0。
针对这个问题，只需要把最后返回的max移到循环内，对孩子做检查就行了，不需要对自己的收益做检查。修改后代码如下。
from collections import defaultdict
n = int(input())
res = []
send = defaultdict(list)
for i in range(n):
a, b = [int(i) for i in input().split(' ')]
res.append(a)
b -= 2
send[b].append(i)
me = {}
def getMaxValue(k):
if k in me:
return me[k]
r = res[k]
if k in send:
for i in send[k]:
r += max(getMaxValue(i), 0)
me[k] = r % 1000000003
return me[k]
a = 0
for i in range(n):
a = max(getMaxValue(i), a)
print(a)
至于第三题，是一个简化版的后端模板语言渲染工具，思考了一阵子，发现代码量会很大，放弃了。
虽然承认自己做的很烂，但还是想写出来留个记录，同时也为了大家讨论吧。
