bzoj 1150 CTSC:[CTSC 2007]データバックアップBackup Backup

5418 ワード

欲張る BZOJ

Description
IT会社では、大規模なオフィスビルやオフィスビルのコンピュータデータをバックアップしています.しかし、データバックアップの仕事は退屈なので、異なるオフィスビルを互いにバックアップし、家に座ってコンピュータゲームを楽しむシステムを設計したいと思っています.オフィスビルは同じ通りにあることが知られています.あなたはこれらのオフィスビルにペアを組むことにしました(2つのグループ).各オフィスビルは、この2つの建物の間にネットワークケーブルを敷設することで、互いにバックアップすることができます.しかし、ネットワークケーブルの費用は高い.ローカルテレコムはK本のネットワークケーブルしか提供できません.これは、K対オフィスビル(または合計2 Kのオフィスビル)のバックアップのみを手配できることを意味します.いずれのオフィスビルも唯一のペアグループに属している(言い換えれば、この2 Kのオフィスビルはきっと違うに違いない).また、電信会社はネットワークケーブルの長さ(キロ数)で料金を徴収する必要があります.そのため、このK対オフィスビルを選択して、ケーブルの全長をできるだけ短くする必要があります.言い換えれば、このK対のオフィスビルを選択して、各対のオフィスビル間の距離の和(総距離)をできるだけ小さくする必要があります.次の例では、5人のお客様がオフィスビルが1つの街にあると仮定します.下図に示します.この5つのオフィスビルは、通りの起点から1 km、3 km、4 km、6 km、12 kmに位置しています.電信会社はK=2本のケーブルしか提供していません.
上記の例では、1番目と2番目のオフィスビルを接続し、3番目と4番目のオフィスビルを接続するのがベストです.これにより、K=2本のケーブルを要求通りに使用することができる.1本目のケーブルの長さは3 km-1 km=2 km、2本目のケーブルの長さは6 km-4 km=2 kmです.このペアリングスキームは,距離の和の最小の要件を満たす全長4 kmのネットワークケーブルを必要とする.Input
入力された第1行は、n(2≦n≦100,000)がオフィスビルの数を表し、k(1≦k≦n/2)が利用可能なネットワークケーブルの数を表す整数nおよびkを含む.次のn行は、各オフィスビルから通りの起点までの距離を示す整数(0≦s≦1000,000,000)のみを含む.これらの整数は、小さい順に表示されます.Output
出力は、2 K個の異なるオフィスビルをk対に接続するために必要なネットワークケーブルの最小総長を与える正の整数で構成されるべきである.
Sample Input
5 2
1
3
4
6
12 Sample Output
4
问题解:もうだめだ、ますます怠けて、问题の大意さえ书きたくない233、まずはっきりしたのは私达が选んだ線分がきっと隣の2つの建物の间のもので、それから私达は1つのとても简単な费用の流れのアルゴリズム2333を考えることができて、データの范囲を见ると実行できません.私たちは1つの非常にSB甚だしきに至ってはサンプルさえ过ごすことができない贪欲さを考えることができて、毎回最小を选ぶことができて、しかしこれは私达に1つの启発を与えて、连続の3つのセグメントの中间の最も小さい时、両侧のさもなくばすべてさもなくばすべていないで、さもなくばいずれの情况も中间の交换で答えを更に优しくすることができて、だから私达は最小の点を加える时に両侧のセグメントを1つの全体と见なすことができて、私たちは両側の線分の長さと中間線分の長さを減らしてスタックに挿入して、このようにこの点を選んだのは私が中間の点を放棄して両側の点を選んだことを意味して、この法則の同じ原理は区間に適用して、しかも私たちはこのようにするたびにちょうど新しい点を加えることを発見して、だからK回をすればいいです.(チェーンポインタの書き込みが掛かった、ストップした書き込み配列233

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define INF 1e9
#define int long long
struct wire
{
    int l,r;
    int key;
    int num;
    bool operator < (wire b) const
    {
        return key>b.key;
    }
}w[500000];
priority_queue q;
int d[500000];
bool pd[500000];
main()
{
    int n,k;
    scanf("%lld%lld",&n,&k);
    w[0].key=INF;
    w[0].l=w[0].r=0;
    w[0].num=0;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&d[i]);
        if(i!=1)
        {
            w[++cnt].key=d[i]-d[i-1];
            w[cnt].num=cnt;
            w[cnt].l=cnt-1;
            if(i!=n) w[cnt].r=cnt+1;
            q.push(w[cnt]);
        }
    }
    long long ans=0;
    while(k>0)
    {
        wire t=q.top();
        q.pop();
        int num = t.num, l = w[num].l, r = w[num].r;
        if(pd[num]) continue;
        pd[num]=pd[l]=pd[r]=1;
        ans+=w[num].key;
        k--;
        cnt++;
        w[cnt].num=cnt;
        w[cnt].key=w[l].key+w[r].key-w[num].key;
        w[cnt].l=w[l].l;
        w[cnt].r=w[r].r;
        w[w[l].l].r=cnt;
        w[w[r].r].l=cnt; 
        q.push(w[cnt]);
    }
    printf("%lld
",ans);
    return 0;
}

[プログラマー/python]ネットワーク

NodeJSとexpressJSを使用してサーバを処理する