blue_jamのTopCoder日記

SRM492 Div1 Easy

SRM, Practice | 15:11

概要

木の高さが一直線上に並ぶようにそろえる．

主人公は時間を巻き戻せるので，木は短くすることができる．

最小でいくつの木を短くすればいいだろうか．

解法

全探索．

2本の木を順番に選んで，いくつ木を短くすればいいか調べる．

#define EPS (1e-10)
class TimeTravellingGardener {
public:
    int determineUsage(vector <int> distance, vector <int> height) {
        int n = height.size();
        int res = n - 1;
        vector<int> v;
        v.push_back(0);
        for(int i=0;i<n;++i){
            v.push_back(v[i] + distance[i]);
        }
        for(int a=0;a<n;++a){
            for(int b=0;b<n;++b){
                double t = double(height[b] - height[a]) / (v[b] - v[a]);
                double s = height[a] - t * v[a];
                int cnt = 0;
                bool flag = true;
                for(int i=0;i<n;++i){
                    if(s + t * v[i] < - EPS){
                        flag = false;
                    }
                    else if(height[i] - EPS < s + t * v[i] && s + t * v[i] < height[i] + EPS){
                    }
                    else if(height[i] + EPS > s + t * v[i]){
                        ++cnt;
                    }
                    else{
                        flag = false;
                    }
                }
                if(flag) res = min(cnt, res);
            }
        }
        return res;
    }
};