SRM 586 DIV1 L1

可以化简为求n条线段的最大覆盖问题，需要注意的是对于实数而言。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <string.h>
using namespace std;

class PiecewiseLinearFunction {
private:
    map<int, int> Y2i;
    int value[100];
public:
    int maximumSolutions(vector <int> Y) {
        for (int i = 0; i < Y.size(); i++) {
            Y2i[Y[i]] = 0;
        }
        int no = 0;
        for (map<int, int>::iterator it = Y2i.begin(); it != Y2i.end(); it++) {
            //cout << it->first << endl;
            it->second = 2 * no++;
        }

        memset(value, 0, sizeof(value));

        for (int i = 0; i < Y.size() - 1; i++) {
            int d = Y[i + 1] - Y[i];
            if (d == 0) {
                return -1;
            } else {
                d = d / abs(d);
                int begin = Y2i[Y[i]];
                int end = Y2i[Y[i + 1]];
                while (begin != end) {
                    value[begin]++;
                    begin += d;
                }
            }
        }
        value[Y2i[Y.back()]]++;

        int ans = 0;
        for (int i = 0; i < 100; i++) {
            ans = max(ans, value[i]);
        }
        return ans;
    }
};