189 8069 5689

SRM479-创新互联

250pt：SRM479

题意：有一排一共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 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 #include 
 10 #include 
 11 #include 
 12 #include 
 13 #include 
 14 #include 
 15 #include 
 16 #include 
 17 #include 
 18 #include 
 19 #include 
 20 #include 
 21 #include 
 22 #include 
 23 #include 
 24 #include 
 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 VI;
 35 typedef vector VS;
 36 typedef vector VD;
 37 typedef long long LL;
 38 typedef pair PII;
 39 int A[500], B[500], F[500], P[500], T[500];
 40 vector 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 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  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-创新互联
分享路径：http://cdxtjz.cn/article/cspgoo.html

其他资讯