CE但不懂求助
  • 板块学术版
  • 楼主sunyizhe
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/20 23:28
  • 上次更新2024/11/21 07:00:41
查看原帖
CE但不懂求助
481330
sunyizhe楼主2024/11/20 23:28

代码见下,哪里比较的问题?

//程序算法:双指针
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

struct Student{
    int x,w;
}a[N];

int Hash[N],cnt[N],n;

bool cmp(const Student& a,const Student& b)
{
    return a.x<b.x;
}

void fast_read()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    
    fast_read();
    
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].w,Hash[i]=a[i].w;

    sort(Hash+1,Hash+n+1);
    int nn=unique(Hash+1,Hash+n+1)-Hash-1;
    sort(Hash+1,Hash+n+1);
    sort(a+1,a+n+1,cmp);

    int l=0,r=1,tot=0,ans=INT_MAX; //左闭右开
    while(l<r)
    {
        if(r<=n)
        {
            r++;
            int id=lower_bound(Hash+1,Hash+n+1,a[r-1])-Hash;
            if(cnt[id]++==0)tot++;
        }

        while(tot>nn)
        {
            int id=lower_bound(Hash+1,Hash+n+1,a[l])-Hash;
            l++;
            if(--cnt[id]==0)tot--;
        }

        ans=min(ans,r-l);
    }

    cout<<ans<<'\n';
    return 0;
}
2024/11/20 23:28
加载中...