首页 > ACM题库 > HDU-杭电 > HDU 1571 下沙小面的(1)-模拟-[解题报告] C++
2013
12-12

HDU 1571 下沙小面的(1)-模拟-[解题报告] C++

下沙小面的(1)

问题描述 :

Lele 在下沙高校中有很多同学,所以他有时间也经常到处去看望同学(顺便蹭饭)。
在下沙,最便宜方便的交通工具莫过于小面的了。
坐得多了,Lele有时候也想,如果将来失业了,能够在下沙开开小面的,也是多么幸福的啊。

终于有一天,他如愿当上了小面的的司机。为了更好的服务客户,他订立了一些开车的法则。

1.当有人要求上车时,如果不是下面这两种情况,他就会让人上车。
2.有些人会因为迷路,往往不知道自己在哪里。比如身在城市1,他也会要求Lele把他送到城市1。这时,Lele当然具有商人诚信的原则,告诉他这个情况,并且不会让他上车。
3.由于小面的的座位只有7个(不包括司机Lele的驾驶座),如果当时车上已经有7个人,Lele就不会让人再上车了。
4.在没人上车时,Lele会看车内谁最早上车,然后把他送到目的地,当然,车内其他要去这个地方的人也会一起下车。然后车停在那个位置
5.如果车内已经没乘客了,Lele就会在原地等着,直到下一个顾客上门。否则Lele在那个地方重复前面的法则。

现在,告诉你Lele一天面对到的情况,请帮他计算一下,他一天一共开了多少距离。

输入:

本题目包含多组测试。最后一组测试后有一个0代表结束。
每组测试第一行有一个整数NCity(3<=NCity<=30)表示下沙一共有多少个站点(站点从0开始标号)。
然后给你一个 NCity * NCity 的矩阵,表示站点间的两两距离。即这个矩阵中第 i 行 第 j 列的元素表示站点 i 和站点 j 的距离。(0<=距离<=1000)
再然后有一个正整数 K , 表示接下来有K个指令。每个指令占一行。
当指令开头为 UP 的时候,接下来有一个整数 T ,表示在面的所在位置有一个要去站点T(0<=T<NCity)的人要上车。
当指令为 GO 的时候,表示Lele要执行法则4,送某些乘客下车。
当然,如果车上当时没有乘客的话,你就可以忽略这个指令。

注意:
在每组测试开始的时候,Lele的面的总是停在站点0,且车为空
如果在T个指令都结束之后,还发现有人没下车,则你可以忽略他们。

输出:

最后在一行内输出一个整数,表示Lele的面的一共开了多少距离。

样例输入:

3
0 1 2
1 0 3
2 3 0
9
UP 1
UP 2
GO
UP 2
GO
GO
UP 2
UP 1
GO
0

样例输出:

7

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1571

思路:纯模拟,vector的应用。

#include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<vector>
 using namespace std;
 #define MAXN 33
 int map[MAXN][MAXN];
 int n;
 
 int main(){
     while(~scanf("%d",&n)&&n){
         for(int i=0;i<n;i++){
             for(int j=0;j<n;j++){
                 scanf("%d",&map[i][j]);
             }
         }
         int _case;
         scanf("%d",&_case);
         vector<int>vet;
         vector<int>::iterator iter;
         int start=0,end,dist=0;
         while(_case--){
             char str[10];
             scanf("%s",str);
             if(str[0]=='U'){
                 scanf("%d",&end);
                 if(end==start||vet.size()==7)continue;
                 vet.push_back(end);
             }else {
                 if(!vet.empty()){end=vet.front();dist+=map[start][end];start=end;}
                 iter=vet.begin();
                 while(iter!=vet.end()){
                     if((*iter)==end){
                         iter=vet.erase(iter);//返回指向vector的下一个位置
                     }else 
                         iter++;
                 }
             }
         }
         printf("%d\n",dist);
     }
     return 0;
 }

 

 

解题报告转自:http://www.cnblogs.com/wally/archive/2013/04/30/3052089.html