模拟题
1 /* 2 模拟 3 注意：相同一边的车有先后顺序！ 4 */ 5 #include<stdio.h> 6 #include<string.h> 7 #include<stdlib.h> 8 #include<algorithm> 9 #include<iostream> 10 #include<queue> 11 #include<map> 12 #include<stack> 13 #include<set> 14 #include<math.h> 15 using namespace std; 16 typedef long long int64; 17 //typedef __int64 int64; 18 typedef pair<int64,int64> PII; 19 #define MP(a,b) make_pair((a),(b)) 20 const int maxn = 100000; 21 const int inf = 0x7fffffff; 22 const double pi=acos(-1.0); 23 const double eps = 1e-8; 24 25 struct Node{ 26 int len; 27 int id; 28 }a[ maxn ]; 29 30 bool Judge( int n ){ 31 bool f = true; 32 for( int i=n;i>=1;i-- ){ 33 if( a[i].id!=0 ){ 34 f = false; 35 break; 36 } 37 } 38 if( f==true ) return true; 39 else return false; 40 } 41 42 int main(){ 43 int T; 44 //freopen("in.txt","r",stdin); 45 //freopen("out.txt","w",stdout); 46 scanf("%d",&T); 47 while( T-- ){ 48 int LL,n; 49 scanf("%d%d",&LL,&n); 50 LL *= 100; 51 char t[ 10 ]; 52 for( int i=1;i<=n;i++ ){ 53 scanf("%d %s",&a[i].len,t); 54 if( t[0]=='l' ) a[i].id = -1; 55 else a[i].id = 1; 56 } 57 int ans = 0; 58 int cur = -1; 59 int L,R; 60 L = R = 1; 61 while( 1 ){ 62 if( Judge( n )==true ) 63 break; 64 //judge 65 cur = -1; 66 int sum = 0; 67 for( ;L<=n;L++ ){ 68 if( a[L].id!=cur ) continue; 69 if( sum+a[L].len<=LL ){ 70 sum += a[L].len; 71 a[ L ].id = 0; 72 } 73 else break; 74 } 75 ans ++; 76 if( Judge( n )==true ) 77 break; 78 //left 79 sum = 0; 80 cur = 1; 81 for( ;R<=n;R++ ){ 82 if( a[R].id!=cur ) continue; 83 if( sum+a[R].len<=LL ){ 84 sum += a[R].len; 85 a[ R ].id = 0; 86 } 87 else break; 88 } 89 ans++; 90 //right 91 } 92 printf("%d ",ans); 93 } 94 return 0; 95 }