暴力求调,最后俩个测试点WA

P8661 [蓝桥杯 2018 省 B] 日志统计

TCww @ 2024-11-23 11:38:37

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,d,k;
    cin>>n>>d>>k;
    vector<vector<int> >res(n,vector<int>(2,0));
    for(int i=0;i<n;i++)
    {
        cin>>res[i][0]>>res[i][1];
    }
    // 按时间优先排序,如果时间相同按 ID 排序
    sort(res.begin(), res.end(), [](const vector<int> &a, const vector<int> &b)
    {
        if (a[1] == b[1]) 
            return a[0] < b[0]; // ID相同按 时间 排序
        return a[1] < b[1];     // 按ID排序
    });
    // for(int i=0;i<n;i++)
    // {
    //     cout<<res[i][0]<<" "<<res[i][1]<<endl;
    // }
    int startp=0;
    int temp,currentid,coin;
    int endp=res[n-1][1];
    while(startp<n)
    {
        currentid=res[startp][1];
        temp=startp;
        coin=0;//在这里别耍小聪明,不然如果对于k=1且最后只有一个元素会漏判
        while(temp<n&&res[temp][1]==currentid&&coin<k)
        {
            if(res[temp][0]-res[startp][0]<d)
            {
                coin++;
                if(coin>=k)
                {
                    cout<<res[startp][1]<<endl;
                    //跳转下一个id
                    while(startp<n&&res[startp][1]==currentid)startp++;
                    break;
                }    
            }
            temp++;
        }
        //这里不能忘记更新
        while(startp<n&&res[startp][1]==currentid)startp++;
        //大于最大的id此时可以退出
        if(startp>=n)break;
    }

    return 0;
}

|