描述

• 這里有一輛賽車比賽正在進行，賽場上一共有N輛車，分別稱為個g1，g2……gn。賽道是一條無限長的直線。最初，gi位于距離起跑線前進ki的位置。比賽開始后，車輛gi將會以vi單位每秒的恒定速度行駛。在這個比賽過程中，如果一輛賽車曾經處于領跑位置的話（即沒有其他的賽車跑在他的前面），這輛賽車最后就可以得獎，而且比賽過程中不用擔心相撞的問題。現在給出所有賽車的起始位置和速度，你的任務就是算出那些賽車將會得獎。

分析

• 暴力枚舉每輛車是否可以得獎.

• 計算該車可以領跑的時間區間 [L, R], 初始化 L = 0, R = INF. 每次和另一輛車進行比較, 維護這個區間, 直到所有的車已經比較過或者 L > R.

• 暴力時間復雜度 O(n^2), 但數據沒有卡.

#include #include #include using namespace std;const double INF = 1e18; const int maxn = 10000 + 10;int p[maxn], v[maxn]; vectorans;int main() {int n;scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &p[i]);for(int i = 1; i <= n; i++) scanf("%d", &v[i]);for(int i = 1; i <= n; i++) {bool win = 1;double L = 0, R = INF;for(int j = 1; j <= n; j++) {double x = 0.0, y = INF;if(v[i] < v[j]) y = (double)(p[i]-p[j]) / (v[j]-v[i]);else if(v[i] > v[j]) x = (double)(p[j]-p[i]) / (v[i]-v[j]);else if(p[i] < p[j]) y = -INF;L = max(L, x);R = min(R, y);if(L > R) { win = 0; break; }}if(win) ans.push_back(i);}int m = ans.size();printf("%d\n", m);for(int i = 0; i < m-1; i++) printf("%d ", ans[i]);printf("%d\n", ans[m-1]);return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ-3190-赛车-JLOI2013-暴力枚举的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。