TopCoder SRM678(Div.1) Normal TheEmpireStrikesBack

Posted on By 二价氢

题目大意

个目标,攻击时导弹要瞄准一个目标,之后摧毁对角线所描述的矩形之内的所有目标。

的最小值,使得能在次攻击内摧毁所有目标。

解法

显然,如果点是目标,那么点就能够跟一起被摧毁,所以不用考虑。至于如何找出,显然用二分就够了。

凭借着这一点,我们可以预先排序一次,之后找出右上方没有目标的目标,之后将对它进行讨论。

接下来是贪心的部分,首先我们确定攻击范围的的最大值,接着找到一个目标,使得的最大值点恰能被攻击到,接着找到我们能攻击到的的最大值,则我们这一次攻击范围就是这一块,如此重复次,就能够确定所有点是否都能被攻击到。

总的复杂度是

Code

#define maxn (100000 + 1)
#define mod (1000000007)
#define x first
#define y second
class TheEmpireStrikesBack {
public:
    vector<pair<long long, long long> > pt;
    vector<pair<long long, long long> > p;
    bool check(int t, int m) {
        int nw = 0;
        for (int i = 0; i < m; i++) {
            int mxy = p[nw].y;
            int mxx = -1;
            while (nw + 1 < p.size() && p[nw + 1].y + t >= mxy) nw++;
            mxx = p[nw].x;
            while (nw + 1 < p.size() && mxx + t >= p[nw + 1].x) nw++;
            if (++nw == p.size()) return true;
        }
        return false;
    }
    int find(int _AX, int BX, int CX, int _AY, int BY, int CY, int N, int M) {
        long long AX = _AX, AY = _AY;
        int mint = -1;
        pt.clear(), p.clear();
        pt.push_back(make_pair(AX, AY));
        for (int i = 1; i < N; i++)
            pt.push_back(make_pair(AX = ((AX * BX) + CX) % mod, AY = ((AY * BY) + CY) % mod));
        sort(pt.begin(), pt.end());
        for (int i = 0; i < N; i++) {
            while (p.size() && pt[i].y >= p[p.size() - 1].y) p.pop_back();
            p.push_back(pt[i]);
        }
        for (int i = (1 << 30); i; i >>= 1) {
            if (!check(mint + i, M)) mint += i;
        }
        return mint + 1;
    }
};

Level Upper 2016 - TopCoder 500 : 5 / 5