首页 > 代码库 > UVA 1372 - Log Jumping(推理)
UVA 1372 - Log Jumping(推理)
题目链接:1372 - Log Jumping
题意:给定一些n个木板的起始位置和长度k,相重叠的木板可以互相跳跃,求能构成环的最大数量。
思路:先按起始位置排序,然后每次多一个木板就去判断他和前一个和前前一个能不能互相跳跃,如果可以的话就可以多加上这个木板。
代码:
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define max(a,b) ((a)>(b)?(a):(b)) #define INF 0x3f3f3f3f const int N = 5005; int t, n, k, i, start[N]; bool check(int s, int e) { return e - s <= k; } int main() { scanf("%d", &t); while (t--) { int ans = 0; scanf("%d%d", &n, &k); for (i = 0; i< n; i++) scanf("%d", &start[i]); sort(start, start + n); i = 0; while (i < n) { int sum = 1; while (i < n - 1 && ((sum == 1 && check(start[i], start[i + 1])) || (check(start[i], start[i + 1]) && check(start[i - 1], start[i + 1])))) sum++, i++; if (!check(start[i], start[i + 1]) || i == n - 1) i++; ans = max(ans, sum); } printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。