记录下网易4/18笔试

第二题

枚举每个位置n开始的情况，然后循环m次pk：
由于使用set<int>lost记录淘汰的人，时间复杂度是log(n)的,导致超时只过了0.3。
应该直接用vector<int>lost就行时间复杂度为1的检验。</int></int>

#include <bits/stdc++.h>

using namespace std;

int n, m;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        string s;
        cin >> s;
        int result = 0;
        for(int i = 0; i < n; i++){//枚举n种不同的起始点
            int si***t res = n;//人数
            vector<int> lost(n);//之前用的set<int>lost，查找时间增加。

            int first = i;
            int next = first + 1;
            while(size--)
            {
                if(next == n) {
                    next = 0;
                    while(lost[next]) next++;
                }
                if(s[first] == s[next]){
                    first = next;//打平
                    next++;
                    while(lost[next]) next++;
                }else if((s[first] == 'R' && s[next] == 'S') || (s[first] == 'S' && s[next] == 'C') || (s[first] == 'C' && s[next] == 'R')){
                    lost[next] = 1;
                    next++;
                    while(lost[next]) next++;//淘汰的人不在选
                    res --;
                    if(lost.size() == n - 1) break;
                }else if((s[first] == 'R' && s[next] == 'C') || (s[first] == 'S' && s[next] == 'R') ||(s[first] == 'C' && s[next] == 'S')){
                    lost[first] = 1;
                    first = next;
                    next++;
                    while(lost[next]) next++;
                    res--;
                    if(lost.size() == n - 1) break;
                }
            }
            result = max(result, res);
        }
        cout << result <<endl;
    }
}

第三题

思路：使用类似对顶堆的形式存储积分(其实可以直接一个multiset就行)，用map存储用户和积分，用set存储那些人获奖。
问题：过了样例但是结果提交是0。检查发现没有判断再次闯关时，可能新分数比旧分数小。(若有其他问题，望指出)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;

        map<int, int> nums;//每位参赛的
        multiset<int, greater<int>> down;
        multiset<int> up;
        set<int> people;//哪些人获奖了

        int res = 0;//奖品
        for(int i = 0; i < n; i++){
            int p, s;
            cin >> p >>s;//p是id,s是分值
            //第一次插入这个id的p
            if(nums.count(p) == 0){
                nums.emplace(p, s);
                if(down.empty() || s <= *down.begin()) down.emplace(s);
                else up.emplace(s);

                if(down.size() > up.size() + 1) {
                    up.emplace(*down.begin());
                    down.erase(down.begin());
                }
                if(up.size() > down.size()){
                    down.emplace(*up.begin());
                    up.erase(up.begin());
                }
                //偶数个人
                if((up.size() + down.size()) % 2 == 0){
                    double x = (double)(*up.begin() + *down.begin()) / 2;
                    if((x - s == 0) && !people.count(p)) {
                        res++;
                        people.emplace(p);
                    }//等于中位数并且没拿过
                }else{
                    if(s == *down.begin() && !people.count(p)){
                        res++;
                        people.emplace(p);
                    }
                }
            }else if(nums.count(p) && nums[p] >= s) continue;//之前漏了这句
            else{//更新分数
                int y = nums[p];//之前p这个人的分值
                nums[p] = s;
                if(down.count(y)) down.erase(down.find(y));
                else{
                    up.erase(up.find(y));
                }

                if(down.size() > up.size()) up.insert(s);
                else down.insert(s);

                if((up.size() + down.size()) % 2 == 0){
                    double x = (*up.begin() + *down.begin()) / 2;
                    if((x - s == 0) && !people.count(p)) {
                        res++;
                        people.emplace(p);
                    }//等于中位数并且没拿过
                }else{
                    if(s == *down.begin() && !people.count(p)){
                        res++;
                        people.emplace(p);
                    }
                }
            }
        }
        cout << res <<endl;
    }
}