SRM479-創(chuàng)新互聯(lián)

250pt：SRM479

題意：有一排一共44,777,777個人，每個人需要咖啡或者茶，隊伍的頭部有一臺飲料機，有一個空姐負責給所有人送飲料，她一開始在也頭部?？战隳靡粋€水壺，一開始是空的，可以在飲料機的地方加最多7個單位的咖啡或者茶，加一次要47秒?？战阍谙噜徫恢靡苿有枰?秒，空姐給一個人倒茶或者咖啡需要4秒?，F(xiàn)在告訴你哪些乘客需要茶（最多50個），問最優(yōu)策略下，空姐需要多少時間可以給所有乘客倒好飲料并且回到隊列頭。

創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務領域包括：網站制作、成都做網站、企業(yè)官網、英文網站、手機端網站、網站推廣等服務，滿足客戶于互聯(lián)網時代的江寧網站設計、移動媒體設計的需求，幫助企業(yè)找到有效的互聯(lián)網解決方案。努力成為您成熟可靠的網絡建設合作伙伴！

思路：直接枚舉

500pt：

題意：有n<=477個城市，然后一些城市之間會有航班，每個航班有起飛和到達站、飛行時間，有一個航班開始時間，還有一個周期，從開始時間開始，每隔一個周期有一班飛機起飛?，F(xiàn)在有一個人要從1飛到n，保證1到n之間沒有直接的航班，于是必須至少要換一次航班。每次換航班都有一個等待時間，所有等待時間中的最小值就是一個保險系數(shù)?，F(xiàn)在要在t<=1,000,000,000的時間內從1到達n，問可以達到的大保險系數(shù)是多少。
思路：直接二分答案，那么接下來就是一個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-創(chuàng)新互聯(lián)
文章起源：http://muchs.cn/article0/cspgoo.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網站收錄、搜索引擎優(yōu)化、品牌網站設計、企業(yè)網站制作、動態(tài)網站、用戶體驗

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)

搜索引擎優(yōu)化