资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

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://cdkjz.cn/article/cspgoo.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
教育培训网站建设方案成都纯水机四川雅安服务器托管瑞捷酒店用品成都网站推广鳄鱼养殖公司网站建设公路钻孔机宜宾网站建设力比特机械

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图