绵阳东辰国际test10.11

其实当时就觉得很像奶酪这道题，但思维固执了，就再也没往下想了

首先很清晰的二分答案，

再就考虑check函数怎么维护了，

结合奶酪那道题，也用并查集维护

将上界和下界分别当做一个限制点

如何判断二分的答案能否走过去呢

只要上界与下界不在同一个集合就可

code by hs

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 510
#define eps 1e-6
template<typename T>T read()
{
    T res=0;
    int sym=1;
    char cc=getchar();
    while(!isdigit(cc)&&cc!='-')cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    while(!isdigit(cc))cc=getchar();
    while(isdigit(cc))res=res*10+cc-'0',cc=getchar();
    return res*sym;
}
template<typename T>void read(T &o)
{
    o=read<T>();
}
template<typename T,typename... Other>void read(T& a,Other&... b)
{
    a=read<T>();
    read(b...);
}
int n,L,x[maxn],y[maxn],fa[maxn];
int find(int x)
{
    return fa[x]==x? x:fa[x]=find(fa[x]);
}
bool check(double o)
{
    for(int i=1;i<=n+2;i++)
        fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        if(y[i]-o<-eps)
            fa[find(i)]=find(n+1);
        if(y[i]+o>L+eps)
            fa[find(i)]=find(n+2);
        if(find(n+1)==find(n+2))
            return false;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<o*o-eps)
            {
                fa[find(i)]=find(j);
            }
            if(find(n+1)==find(n+2))
                return false;
        }
    }
    return find(n+1)!=find(n+2);
}
int main()
{
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    read(n,L);
    for(int i=1;i<=n;i++)
        read(x[i],y[i]);
    double l=0,r=L;
    for(int i=1;i<=30;i++)
    {
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.3lf\n",(l+r)/2);
    return 0;
}

反正我坚信我是对的

code by wzxbeliever

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&(-x)
#define il inline
#define ri register int
using namespace std;
const int maxn=5e4+5;
int T,n;
int a[maxn],vis[maxn];
struct node{
    int id,val;
    bool friend operator <(node a,node b){return a.val<b.val;}
}tmp;
priority_queue<node>Q;
int main(){
    //freopen("A.in","r",stdin);
//  freopen("A.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        ll sum=0;int num=0;memset(vis,0,sizeof(vis));
        while(!Q.empty())Q.pop();
        for(ri i=1,x;i<=n;i++){scanf("%d",&x);
        tmp.id=i,tmp.val=-x;
        Q.push(tmp),Q.push(tmp);
        ll t=x+Q.top().val;
        vis[Q.top().id]++;
        //cout<<"t="<<t<<endl;
        sum+=t;
        Q.pop();
        }
    //  while(!Q.empty())printf("%d ",Q.top().val),Q.pop();
        for(ri i=1;i<=n;i++)if(vis[i]==2)num++;num<<=1;
        cout<<sum<<" "<<num<<endl;
    }
    return 0;
}
/*
2
3
1 2 3
3
3 2 1
*/

维护一个小根堆，每次加入元素两次，如果最后该元素被弹出了两次，则它一定是买的