【BZOJ 1208】[HNOI2004]宠物收养所

在这里输入题意

【题解】

用set搞。
(因为规定了不会有相同特点值的东西。
所以可以不用multiset.
那么每次用lower_bound找离它最近的配对就好了

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll MOD = 1000000;

int n;

set<ll> myset[2];

ll ans = 0;

int main()

{

    scanf("%d",&n);

    for (int i = 1;i <= n;i++){

        int a,b;

        scanf("%d%d",&a,&b);

        myset[a].insert(b);

        for (int j = 0;j<=1;j++)

            if ((int)myset[j].size()==1 && (int)myset[1-j].size()>0){

                ll x = (*myset[j].begin());

                myset[j].erase(myset[j].begin());

                set<ll>::iterator temp = myset[1-j].lower_bound(x);

                if (temp==myset[1-j].begin()){

                    //全都大于等于x

                    ans = (ans+(*temp)-x)%MOD;

                    myset[1-j].erase(temp);

                    break;

                }else if (temp==myset[1-j].end()){

                    //全都比x来的小

                    temp--;

                    ans= (ans + x-(*temp))%MOD;

                    myset[1-j].erase(temp);

                }else{

                    ll temp1 = abs(x-(*temp));

                    temp--;

                    ll temp2 = abs(x-(*temp));

                    if (temp2<=temp1){

                        ans=(ans + temp2)%MOD;

                        myset[1-j].erase(temp);

                    }else{

                        ans=(ans + temp1)%MOD;

                        temp++;

                        myset[1-j].erase(temp);

                    }

                }

            }

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

【BZOJ 1208】[HNOI2004]宠物收养所

最新文章

热门文章