http://acm.pku.edu.cn/JudgeOnline/problem?id=1727
题目大意:给定一些点的坐标代表“事件”,每个“事件”可以有一些“因事件”,只要“因事件”的坐标落在给定不等式确定的范围之内即可。另给定数m表示至多有m个“因事件”。求对于给定的所有事件,它们的“因事件”中,最早发生的那一个事件的最迟发生时间(即最大的纵坐标)。
为了方便,把题目中事件的记法(t, x)改为(x, y),t就相当于纵坐标。我这么想的,把那个不等式变个形,不难发现,对于一个事件(x, y)来说,能够导致它的“因事件”必然落在这样一个范围:过(x, y)分别做斜率为1和-1的直线,这两条直线下方的
区域就是“因事件”可能存在的范围。要求的纵坐标t,最大可能的值显然是所有给定的点中最小的纵坐标,最小可能的值根据题目的数据范围也能够定出。这个范围是有序的,t值越大越可能是最优的解。于是对这个区间进行二分,然后验证对于这个t,能否用不超过m个“因事件”来导致所有的点。
这个验证的过程就比较简单了。例如要验证t,对于给定的所有事件点,对它们按照x坐标升序排序,x坐标相等的按y升序排,则可以计算出,对于要验证的纵坐标t,每个点的“因事件”在y=t这条直线上可能存在的坐标范围。遍历排序后的所有点,尽可能的计算出相邻两个点的“可能范围”的相交区间,若没有相交,则需要新增一个“因事件”点。这样算出来需要的总点数如果不超过m则记录答案,然后继续二分。
#include <cstdio>
#include <algorithm>
int n, m;
struct point {
int x, y;
} p[100000];
bool cmp(const point &a, const point &b) {
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
bool check(int y) {
int last_b, last_e, b, e, count;
last_b = y - p[0].y + p[0].x;
last_e = p[0].y - y + p[0].x;
count = 1;
for (int i = 1; i < n; i++) {
b = y - p[i].y + p[i].x;
e = p[i].y - y + p[i].x;
if (last_e < b) {
++count;
last_b = b;
last_e = e;
}
else if (last_b <= b && b <= last_e && last_e <= e)
last_b = b;
else if (last_b <= b && e <= last_e) {
last_b = b;
last_e = e;
}
if (count > m)
return false;
}
return true;
}
int main() {
int cases, ymin, ymax;
scanf("%d", &cases);
for (int caseid = 1; caseid <= cases; caseid++) {
scanf("%d%d", &n, &m);
scanf("%d%d", &p[0].y, &p[0].x);
ymax = p[0].y;
for (int i = 1; i < n; i++) {
scanf("%d%d", &p[i].y, &p[i].x);
if (p[i].y < ymax)
ymax = p[i].y;
}
std::sort(p, p + n, cmp);
ymin = -2000010;
int low = ymin, high = ymax, mid, ans;
while (low <= high) {
mid = (low + high) >> 1;
if (check(mid)) {
ans = mid;
low = mid + 1;
}
else
high = mid - 1;
}
printf("Case %d: %d\n", caseid, ans);
}
return 0;
}
分享到:
相关推荐
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
北大POJ2002-Squares 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3436-ACM Computer Factory 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
很有用的解题报告。。是acm初级提高的必备资料。。。。。
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
poj 1000-3000部分代码 网上收集
北大POJ3273-Monthly Expense POJ3273-Monthly Expense
北大POJ1159-Palindrome 解题报告+AC代码