TopCoder SRM586 Div1 Easy PiecewiseLinearFunction

概要

直線n本から成るグラフが与えられる、これと直線y=kとの交点の数の最大値を求めよ(kは任意の実数)

サンプル

{0, 1, 0}
2

{1, 0, 2, 0}
3

{0, 1, 0, 1}
3

参考にならない参考画像

解法

僕は座標圧縮で、頂点と頂点の間の数を通る線の数を数えましたが、どうやら 座標をy軸方向に2倍して頂点とその上下の点を通る本数を数えるという方法もあるようです

class PiecewiseLinearFunction {
    public:
    int maximumSolutions(vector<int> Y) {
        int count[100] = {}; //辺と辺の間
        int count2[100] = {}; //頂点
        set<int> p(Y.begin(), Y.end());
        vector<int> v(p.begin(), p.end());
        sort(v.begin(), v.end());//ここまで座標圧縮、vには昇順で重複の取り除かれた頂点の座標が入っている(std::uniqueでも良い)
        for (int i = 0; i < Y.size(); i++) {
            count2[lower_bound(v.begin(), v.end(), Y[i]) - v.begin()]++;
            //頂点を追加(制約が激ユルだからstd::findでも良い)
        }
        for (int i = 0; i < Y.size()-1; i++) {
            if (Y[i]==Y[i+1]) {
                return -1;
            }
            int a = lower_bound(v.begin(), v.end(), Y[i]) - v.begin();
            int b = lower_bound(v.begin(), v.end(), Y[i+1]) - v.begin();
            int b1 = min(a, b), b2 = max(a, b);
            for (int j = b1; j < b2; j++) {
                count[j]++;
                if (j != b1) {
                    count2[j]++;
                }
            }
        }
        return max(*max_element(count, count+v.size()-1), *max_element(count2, count2+v.size()));
    }
};