题目大意
有\(n\)个目标，攻击时导弹要瞄准一个目标\((x, y)\)，之后摧毁对角线\((0,0)-(x + T, y + T)\)所描述的矩形之内的所有目标。
求\(T\)的最小值，使得能在\(m\)次攻击内摧毁所有目标。
解法
显然，如果点\((x, y)\)是目标，那么点\((x', y'),(x' \le x, y' \le y)\)就能够跟\((x,y)\)一起被摧毁，所以不用考虑。至于如何找出\(T\)，显然用二分就够了。
凭借着这一点，我们可以预先排序一次，之后找出右上方没有目标的目标，之后将对它进行讨论。
接下来是贪心的部分，首先我们确定攻击范围的\(y\)的最大值，接着找到一个目标，使得\(y\)的最大值点恰能被攻击到，接着找到我们能攻击到的\(x\)的最大值，则我们这一次攻击范围就是这一块，如此重复\(m\)次，就能够确定所有点是否都能被攻击到。
总的复杂度是\(O(n \log T)\)。
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