250pt：

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

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

思路：直接枚舉

500pt：

題意：有n<=477個(gè)城市，然后一些城市之間會(huì)有航班，每個(gè)航班有起飛和到達(dá)站、飛行時(shí)間，有一個(gè)航班開(kāi)始時(shí)間，還有一個(gè)周期，從開(kāi)始時(shí)間開(kāi)始，每隔一個(gè)周期有一班飛機(jī)起飛?，F(xiàn)在有一個(gè)人要從1飛到n，保證1到n之間沒(méi)有直接的航班，于是必須至少要換一次航班。每次換航班都有一個(gè)等待時(shí)間，所有等待時(shí)間中的最小值就是一個(gè)保險(xiǎn)系數(shù)?，F(xiàn)在要在t<=1,000,000,000的時(shí)間內(nèi)從1到達(dá)n，問(wèn)可以達(dá)到的大保險(xiǎn)系數(shù)是多少。
思路：直接二分答案，那么接下來(lái)就是一個(gè)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

新聞標(biāo)題：SRM479-創(chuàng)新互聯(lián)
文章起源：http://www.rwnh.cn/article0/cspgoo.html

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

廣告

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