社区讨论

双倍经验??

P3069[USACO13JAN] Cow Lineup G参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mj9rsgc8
此快照首次捕获于
2025/12/17 16:49
2 个月前
此快照最后确认于
2025/12/20 10:15
2 个月前
查看原帖
这道题和P3029有什么区别
P3029代码:
CPP
#include<bits/stdc++.h>
using namespace std;

struct cow
{
    int x;
    int id;
};

cow c[50005];
int ans=INT_MAX,sum,n,cnt,r;

map<int,int>a;
map<int,bool>b;

bool cmp(cow a,cow b)
{
    return a.x<b.x;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	cin>>c[i].x>>c[i].id;
    	if(b[c[i].id]==false)
        {
    		sum++;
    		b[c[i].id]=true;
		}
	}
    
    sort(c+1,c+n+1,cmp);
    r=1;
    a[c[1].id]++;
    cnt=1;
    
    for(int i=1;i<=n;i++)
    {
        while(cnt<sum&&r<n)
        {
            r++;
            a[c[r].id]++;
            if(a[c[r].id]==1)
            {
                cnt++;
            }
        }
        
        if(cnt==sum)
        {
            ans=min(ans,c[r].x-c[i].x);
        }
        
        a[c[i].id]--;
        
        if(a[c[i].id]==0)
        {
            cnt--;
        }
    }
    cout<<ans;

    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...