模拟题
/*
模拟
注意:相同一边的车有先后顺序!
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = 100000;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
struct Node{
int len;
int id;
}a[ maxn ];
bool Judge( int n ){
bool f = true;
for( int i=n;i>=1;i-- ){
if( a[i].id!=0 ){
f = false;
break;
}
}
if( f==true ) return true;
else return false;
}
int main(){
int T;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&T);
while( T-- ){
int LL,n;
scanf("%d%d",&LL,&n);
LL *= 100;
char t[ 10 ];
for( int i=1;i<=n;i++ ){
scanf("%d %s",&a[i].len,t);
if( t[0]=='l' ) a[i].id = -1;
else a[i].id = 1;
}
int ans = 0;
int cur = -1;
int L,R;
L = R = 1;
while( 1 ){
if( Judge( n )==true )
break;
//judge
cur = -1;
int sum = 0;
for( ;L<=n;L++ ){
if( a[L].id!=cur ) continue;
if( sum+a[L].len<=LL ){
sum += a[L].len;
a[ L ].id = 0;
}
else break;
}
ans ++;
if( Judge( n )==true )
break;
//left
sum = 0;
cur = 1;
for( ;R<=n;R++ ){
if( a[R].id!=cur ) continue;
if( sum+a[R].len<=LL ){
sum += a[R].len;
a[ R ].id = 0;
}
else break;
}
ans++;
//right
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
poj1379 给予平面内一个点集; 使用模拟退火求出一个点使该点到上述点集内任意一点最短距离最长。
选择了三道经典的二分查找的poj模拟题,有利于读者对二分查找的深刻把握
poj2340,模拟题,使用两个优先队列模拟即可。
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
包含15类的POJ推荐50题,可全面复习或学习算法。 除此外还包含三种级别的水平(初级、中级、高级)应掌握的算法及数据结构及... (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
模拟题 要注意时间的处理 使用优先队列处理请求的事件 进行适当的运算符重载,可以简化代码
poj题目分类,适合acmer学习研究 主流算法: 1.搜索 //回溯 2.DP(动态规划) 3.贪心 4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7....
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,...
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。
Algorithm-Java Algorithms + Data Structures = Programs....最短路径(dijkstra,bellman-ford,floyd,heap+dijkstra)(,,poj1062,poj2253,poj1125,poj2240) 最小生成树(prim,kruskal)(p
总结了多位大神的解题技巧并分享. 运用了模拟法,多种解题思路,都通过了ACM网址的提交Accept。
4. 特别提到了模拟赛的功能,如HUSTOJ的VirtualJudge,可以自行挑选题目模拟比赛。 5. 还提到了一些OJ网站的独特特色,如SPOJ的奇特提交模式、ZJU每月赛等。 总的来说,这是一份经过总结和分类的OJ题库推荐,可以根据...
leetcode中国 MyAlgorithmSolutions 记录我所有的算法/数据结构 目录 ...笔记 数据结构 算法(第四版) 大一题目 HDOJ ...POJ ...蓝桥杯模拟 蓝桥杯学习 bfs 大数 dfs/抽象dfs 逻辑 测试 栈/递归 清华oj入门
Contester-具有模拟参加历史比赛的虚拟赛功能 http://acm.sgu.ru/ Codeforces-不断维护历届题库 http://codeforces.com 首先,要向读者介绍的是历史最悠久,最著名的OJ-西班牙Valladolid大学的【UVaOJ】 ...
主流算法: 1.搜索 //回溯 2.DP(动态规划) 3.贪心 4.图论 //Dijkstra、最小生成...8.模拟 9.数据结构 //并查集、堆 10.博弈论 1、 排序 2、 搜索、回溯、遍历 3、历法 4、 枚举 5、 数据结构的典型算法 6、 动态规划
#POJ 题集 数论 欧几里得/拓展欧几里得算法 1006 1061 搜索 普通搜索 1062, 1088, 2386 剪枝优化 1011 动态规划 背包 1014 高精度 加减乘除 1001 巧妙处理 思维处理 1852 模拟 1017 简单题 水题 1004 1007 1008 枚举...
刷题使人进步 :grinning_face_with_smiling_eyes: 为什么刷题 希望将来项目提升自己的编程能力。 ...模拟题 动态规划 快速幂: 贪心: 图论: 数学: 分治 数据结构 佐治 简单题 搜寻 POJ 动态规划
AlgoHub囊括了 POJ, ZOJ, leetcode, HackerRank 等网站的经典题目(一些质量不高的题目则忽略),且 AlgoHub有非常简单的加题系统,用户不需要写一行代码即可自己添加题目,所以AlgoHub的题库还在飞速增长中。...