T27384: 候选人追踪

heap,lazy delete, http://cs101.openjudge.cn/practice/27384/

【姚博骞 25物院】思路：将在k个人里面和不在k个人里的人的投票数据分别加入两个堆，比较第一个堆最小和第一个堆最大。思路还行但执行起来非常难办对我而言，起码提交了20次没过。要注意的是投票时间间隔中票数都不变，故应当找开始满足的时刻和结束满足的时刻做差。 最后的bug出现在对最末尾的处理，要同时判断存在一个之前满足的时刻并且在这之后没有不满足的时刻才最后要用tmax-tlast。

懒删除的意思就是我不做队列中的删除但是做用数组记录，同时把正确的入队，如果出队的时候发现匹配不上就不管他。

#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#include<unordered_map>
using namespace std;
struct Compareda//return true 时a的优先级小于b
{
    bool operator()(pair<int,int> &a,pair<int,int> &b)
    {
        return a.second<b.second;
    }
};
struct Comparexiao//return true 时a的优先级小于b
{
    bool operator()(pair<int,int> &a,pair<int,int> &b)
    {
        return a.second>b.second;
    }
};
int main()
{
    int n,k;
    vector<pair<int,int>> vote;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        int t,c;
        cin>>t>>c;
        vote.push_back({t,c});
    }
    set<int> s;
    for(int i=0;i<k;i++)
    {
        int p;
        cin>>p;
        s.insert(p);
    }
    sort(vote.begin(),vote.end(),[&s](pair<int,int>&a,pair<int,int>&b)
    {
            return a.first<b.first;
    });
    vector<int> sum(314160,0);
    priority_queue<pair<int,int>,vector<pair<int,int>>,Comparexiao> kgeren;//第一个是序号，第二个是票数
    priority_queue<pair<int,int>,vector<pair<int,int>>,Compareda> qita;
    int ans=0;
    for(int i=1;i<314160;i++)
    {
        if(s.find(i)!=s.end())
            {
                kgeren.push({i,0});
            }
            else
            {
                qita.push({i,0});
            }
    }
    //只要我让k个的最小值比其它的最大值大就行。
    int i=0;
    int flag=0;
    int t_last=-1;
    while(i<n)
    {
        if(k==314159) break;
        while(i<n)
        {
            sum[vote[i].second]++;
            if(s.find(vote[i].second)!=s.end())
            {
                kgeren.push({vote[i].second,sum[vote[i].second]});
            }
            else
            {
                qita.push({vote[i].second,sum[vote[i].second]});
            }
            i++;
            if(i==n||vote[i].first!=vote[i-1].first)
            {
                break;
            }
        }
        while(kgeren.top().second!=sum[kgeren.top().first]||qita.top().second!=sum[qita.top().first])
        {
            if(!kgeren.empty()&&kgeren.top().second!=sum[kgeren.top().first])
            {
                kgeren.pop();
            }
            if(!qita.empty()&&qita.top().second!=sum[qita.top().first])
            {
                qita.pop();
            }
        }
        if(qita.top().second<kgeren.top().second)
        {
            if(flag==0) {t_last=vote[i-1].first;}
            flag=1;
        }   
        else if(flag==1)
        {
            flag=0;
            ans+=vote[i-1].first-t_last;
        }
    }
    if(flag==1&&t_last!=-1)
    {
        ans+=vote[i-1].first-t_last;
    }
    if(k==314159) 
    {cout<<vote[n-1].first;}
    else 
    {cout<<ans;}
    return 0;
}