首页 > 代码库 > UVA 617 - Nonstop Travel（数论+暴力枚举）

UVA 617 - Nonstop Travel（数论+暴力枚举）

2024-07-02 08:18:31   223人阅读

题目链接：617 - Nonstop Travel

题意：给定一些红绿灯，现在速度能在30-60km/h之内，求多少个速度满足一路不遇到红灯。
思路：暴力每一个速度，去判断可不可以，最后注意下输出格式即可
代码：
#include <stdio.h>
#include <string.h>
#include <math.h>
const double esp = 1e-6;
int n, vis[105];
struct D {
    double l;
    int g, y, r;
    void scanf_() {
	scanf("%lf%d%d%d", &l, &g, &y, &r);
    }
} d[10];

bool judge(int vv) {
    double v = vv * 1.0 / 3600;
    for (int i = 0; i < n; i++) {
	double t = d[i].l / v;
	int dd = (int)t / (d[i].g + d[i].y + d[i].r);
	t -= dd * 1.0 * (d[i].g + d[i].y + d[i].r);
	if (t - 1.0 * (d[i].g + d[i].y) > -esp)
	    return false;
    }
    return true;
}

void print() {
    int flag = 1, i = 30;
    for (; i <= 60; i++) {
	if (vis[i]) {
	    printf("%d", i);
	    flag = 0;
	    break;
	}
    }
    i++;
    for (; i <= 60; i++) {
	if (vis[i] && vis[i - 1] == 0)
	    printf(", %d", i);
	else if (vis[i] && vis[i - 1] && vis[i + 1] == 0)
	    printf("-%d", i);
    }
    if (flag) printf("No acceptable speeds.");
    printf("\n");
}

int main() {
    int cas = 0;
    while (~scanf("%d", &n) && n != -1) {
	for (int i = 0; i < n; i++)
	    d[i].scanf_();
	memset(vis, 0, sizeof(vis));
	for (int i = 30; i <= 60; i++) {
	    if (judge(i)) vis[i] = 1;
	}
	printf("Case %d: ", ++cas);
	print();
    }
    return 0;
}


联系
我们