SRM 586 Div1 250 PiecewiseLinearFunction

2013-07-27

03:28 |

(i, Y[i]) で表される折れ線グラフが与えられる。y=?? の直線と折れ線グラフとの交点の数の最大値を求める。
1≦N≦50, -1,000,000,000≦Y[i]≦1,000,000,000

y 座標の区間に -1, +1 を対応させて、yが小さいほうから見ていってカウンタを増減させる line sweep な感じ
x 座標が共有される点の処理が面倒
ガチャガチャガチャ
failed system test

(あとで)

y, y±0.5で全通り調べるほうが簡潔だった。もう少し方針をちゃんと考えるべし。。

accepted in practice

class PiecewiseLinearFunction {
	public:
	int maximumSolutions(vector <int> Y) {
		REP(i, Y.size()) Y[i]*=2;
		int offset[] = {-1, 0, 1};
		ll ans = 0;
		REP(i, Y.size()) {
			REP(oi, 3) {
				ll y = Y[i]+offset[oi];
				ll cnt = 0;
				REP(i, Y.size()) if(Y[i]==y) cnt++;
				REP(i, Y.size()-1) {
					if(Y[i]==Y[i+1]) return -1;
					if(min(Y[i], Y[i+1])<y && y<max(Y[i], Y[i+1])) cnt++;
				}
				ans = max(ans, cnt);
			}
		}
		return ans;
	}
};