题意:有一排一共44,777,777个人,每个人需要咖啡或者茶,队伍的头部有一台饮料机,有一个空姐负责给所有人送饮料,她一开始在也头部。空姐拿一个水壶,一开始是空的,可以在饮料机的地方加最多7个单位的咖啡或者茶,加一次要47秒。空姐在相邻位置移动需要1秒,空姐给一个人倒茶或者咖啡需要4秒。现在告诉你哪些乘客需要茶(最多50个),问最优策略下,空姐需要多少时间可以给所有乘客倒好饮料并且回到队列头。
思路:直接枚举
500pt:
题意:有n<=477个城市,然后一些城市之间会有航班,每个航班有起飞和到达站、飞行时间,有一个航班开始时间,还有一个周期,从开始时间开始,每隔一个周期有一班飞机起飞。现在有一个人要从1飞到n,保证1到n之间没有直接的航班,于是必须至少要换一次航班。每次换航班都有一个等待时间,所有等待时间中的最小值就是一个保险系数。现在要在t<=1,000,000,000的时间内从1到达n,问可以达到的大保险系数是多少。
思路:直接二分答案,那么接下来就是一个spfa判定了。
code:
1 #line 7 "TheAirTripDivOne.cpp"
2 #include <cstdlib>
3 #include <cctype>
4 #include <cstring>
5 #include <cstdio>
6 #include <cmath>
7 #include <algorithm>
8 #include <vector>
9 #include <string>
10 #include <iostream>
11 #include <sstream>
12 #include <map>
13 #include <set>
14 #include <queue>
15 #include <stack>
16 #include <fstream>
17 #include <numeric>
18 #include <iomanip>
19 #include <bitset>
20 #include <list>
21 #include <stdexcept>
22 #include <functional>
23 #include <utility>
24 #include <ctime>
25 using namespace std;
26
27 #define PB push_back
28 #define MP make_pair
29
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33
34 typedef vector<int> VI;
35 typedef vector<string> VS;
36 typedef vector<double> VD;
37 typedef long long LL;
38 typedef pair<int,int> PII;
39 int A[500], B[500], F[500], P[500], T[500];
40 vector<int> g[578];
41 bool vis[500];
42 long long d[500];
43 class TheAirTripDivOne
44 {
45 public:
46 string S;
47 int n, m, limit;
48 void make_flight(){
49 m = 0;
50 // cout << S << endl; 51 int cnt = 0, tmp = 0;
52 for (int i = 0; i < S.size(); ++i){
53 if (S[i] == ','){
54 if (cnt == 0) A[m] = tmp;
55 if (cnt == 1) B[m] = tmp;
56 if (cnt == 2) F[m] = tmp;
57 if (cnt == 3) T[m] = tmp;
58 cnt++;
59 tmp = 0;
60 }
61 else if (S[i] == ' '){
62 P[m++] = tmp;
63 tmp = cnt = 0;
64 } else tmp = tmp * 10 + S[i] - 48;
65 }
66 if (tmp > 0) P[m++] = tmp;
67 for (int i = 0; i <= n; ++i)
68 g[i].clear();
69 for (int i = 0; i < m; ++i)
70 g[A[i]].PB(i);
71 }
72 bool SPFA(int waitTime){
73 for (int i = 1; i <= n; ++i)
74 d[i] = (1LL << 40);
75 queue<int> q;
76 d[1] = -waitTime;
77 vis[1] = true;
78 q.push(1);
79 long long time, r;
80 while (!q.empty()){
81 int u = q.front(), v;
82 for (int i = 0; i < g[u].size(); ++i){
83 v = B[g[u][i]];
84 time = d[u] + waitTime;
85 if (time <= F[g[u][i]]) time = F[g[u][i]];
86 else {
87 r = (time - F[g[u][i]] - 1) / P[g[u][i]] + 1;
88 time = F[g[u][i]] + P[g[u][i]] * r;
89 }
90 if (time + T[g[u][i]] < d[v]){
91 d[v] = time + T[g[u][i]];
92 if (!vis[v]) q.push(v), vis[v] = true;
93
94 }
95 }
96 q.pop();
97 vis[u] = false;
98 }
99 return d[n] <= limit;
100 }
101 int solve(){
102 int l = 1, r = 1000000000, mid;
103 int ret = -1;
104 while (l <= r){
105 mid = (l + r) >> 1;
106 if (SPFA(mid)){
107 l = mid + 1;
108 ret = mid;
109 } else r = mid - 1;
110 }
111 return ret;
112 }
113
114 int find(int N, vector <string> flights, int time)
115 {
116 S = accumulate(flights.begin(), flights.end(), string(""));
117 n = N;
118 limit = time;
119 make_flight();
120 return solve();
121 }
122 };
View Code
新闻标题:SRM479-创新互联
文章起源:https://www.cdcxhl.com/article0/cspgoo.html
成都网站建设公司_创新互联,为您提供网站收录、搜索引擎优化、品牌网站设计、企业网站制作、动态网站、用户体验
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联