USACO 2009 Open Cow Line队列 oj26220

 

题目大意：

输入n，n次操作

操作A：在L(左边)或R(右边)插入一个递增的数

操作D：在L(左边)或R(右边)删除m个数

Sample Input

10A LA LA RA LD R 2A RA RD L 1A LA R

Sample Output

72568

Hint

Input    Resulting Cow Line

A L      1A L      2 1A R      2 1 3A L      4 2 1 3D R 2    4 2A R      4 2 5A R      4 2 5 6D L 1    2 5 6A L      7 2 5 6A R      7 2 5 6 8

 

当时没有想到从一个数组中间开始操作 而一直在坚持两个数组模拟左右

也明知有deque可以用 却没有去尝试 最后卒

数组模拟队列

#include <bits/stdc++.h> using namespace std; int main() { int n; int q[200008]; ///只用一个大数组存 但要注意开大两倍 while(~scanf("%d",&n)) { int tail,head,num=1; tail=head=100004; /// 考虑全部只放在同一边的情况 所以左右都要有足够的空间 while(n--) { char ch,ch1; /// 输入的前面加一个空格 以吸收无用的\r scanf(" %c %c",&ch,&ch1); if(ch=='A') { if(ch1=='L') q[--head]=num++; else q[tail++]=num++; } else { int m; scanf("%d",&m); if(ch1=='R') tail-=m; else head+=m; } } for(int i=head;i<tail;i++) printf("%d\n",q[i]); printf("\n"); } return 0; } View Code

STL deque

#include <bits/stdc++.h> using namespace std; int main() { int n; while(~scanf("%d",&n)) { deque <int> q; int num=1; char ch,ch1; while(n--) { scanf(" %c %c",&ch,&ch1); if(ch=='A') { if(ch1=='L') q.push_front(num++); else if(ch1=='R') q.push_back(num++); } else { int m; scanf("%d",&m); if(ch1=='R') { while(m--) if(!q.empty()) q.pop_back(); } else { while(m--) if(!q.empty()) q.pop_front(); } } } while(!q.empty()) { printf("%d\n",q.front()); q.pop_front(); } printf("\n"); } return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8583048.html

相关资源：JAVA上百实例源码以及开源项目