Algoogle

Algorithm for Programming Contest

PKU 3262 Protecting the Flowers

Category: PKU Tag: greedy

Protecting the Flowers

問題概要


いろんなところに牛がいて, 牛を連れて帰るのにそれぞれ2*T分かかる.
また, それぞれの牛は毎分Dだけ花を破壊する.
花の破壊が最小になるように牛を連れて帰る時, 破壊される花の数を求めよ.

解法


2頭の牛のどちらかを連れて帰る時, どちらを連れて帰るのがいいかを考えるとよい.
2頭の牛をi, jとすると, 牛iを連れて帰る時牛jによって破壊される花の数は2T[i]D[j]
逆の場合は2T[j]D[i]
よってその値が大きい方から連れて帰るべきなのでその値でソートしてgreedyに選択していく.

コード


(3262.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>

using namespace std;

#define int long long
struct cow{
    int t, d;
    cow(){}
    cow(int t, int d):t(t),d(d){}
    bool operator<(const cow &c)const{ return c.t*d > t*c.d;}
};

int N, dest;
cow C[100010];

signed main(){
    scanf("%lld", &N);
    for(int i = 0; i < N; i++){
        int t, d; scanf("%lld%lld", &t, &d);
        C[i] = cow(t, d);
        dest += d;
    }
    sort(C, C+N);
    int ans = 0;
    for(int i = 0; i < N; i++){
        dest -= C[i].d;
        ans += 2*dest*C[i].t;
    }
    printf("%lld\n", ans);
    return 0;
}

Comments