洛谷 P1413 坚果保龄球
2024-09-30 10:20:34
题目描述
PVZ这款游戏中,有一种坚果保龄球。zombie从地图右侧不断出现,向左走,玩家需要从左侧滚动坚果来碾死他们。
我们可以认为地图是一个行数为6,列数为60的棋盘。zombie出现的那一秒站在这一行的第60列,之后每秒向左移动一步。玩家可以随时在屏幕最某一行第一列摆放坚果,这一行的zombie瞬间全被滚过去的坚果碾死。如果zombie走到第1列没有被消灭,如果再向左走,则你的大脑就会被zombie吃掉。
现在有n只zombie!告诉你每只zombie出现的时间以及在出现的行数(可能会同时出现同一位置的僵尸),请问至少需要多少坚果才能消灭所有的zombie。
输入输出格式
输入格式:
第一行一个正整数n,表示zombie数量。
之后n行中,每行两个正整数P和t,分别表示zombie所在行和zombie出现的时间。
输出格式:
一个正整数,最少需要的坚果数。
输入输出样例
输入样例#1:
10
1 1
1 61
2 1
2 60
3 1
3 2
3 3
3 4
4 1
4 99999
输出样例#1:
6
说明
【数据规模】
n<=2000,t<=100000,1<=P<=6
【题目来源】
kkksc03改编
贪心
#include <algorithm>
#include <cstdio> using namespace std; struct node
{
int Line,T;
bool operator<(node a)const
{
if(a.Line==Line) return T<a.T;
else return Line<a.Line;
}
}zombie[];
int n;
int main()
{
scanf("%d",&n);
int Answer=,Maxn;
for(int i=;i<=n;i++)
{
scanf("%d%d",&zombie[i].Line,&zombie[i].T);
Maxn=max(Maxn,zombie[i].T);
}
sort(zombie+,zombie++n);
int i=;
while(i<=n)
{
int pos=zombie[i].Line,T_now=zombie[i].T-;
while(T_now<=Maxn)
{
T_now+=;
while(zombie[++i].Line==pos&&zombie[i].T<=T_now);
if(zombie[i].Line!=pos) {Answer++;break;}
if(zombie[i].T>T_now) {Answer++;break;}
}
}
printf("%d",Answer);
return ;
}
最新文章
- This is a TEST
- Linux IPC Pipe
- Ubuntu 14 安装 “宋体,微软雅黑,WPS Office的symbol、wingdings、wingdings 2、wingdings 3、webding字体,Consolas雅黑混合版编程字体” 等 Windows 7 下的字体
- error CS0103: 当前上下文中不存在名称“ViewBag”
- 使用Jquery+EasyUI进行框架项目开发案例解说之中的一个---员工管理源代码分享
- 【Xamarin挖墙脚系列:IOS-关于手机支持的屏幕方向】
- ArrayList LinkedList Vector
- 防止程序启动两次的方法CreateMutex()
- android面试题之三
- 冒泡排序 最好O(n)平均O(n^2) 选择排序O(n2) 插入排序O(n2)
- 1-STM32物联网开发WIFI(ESP8266)+GPRS(Air202)系统方案数据篇(视频总揽和功能演示)
- lvs 初始 第一章
- php7与之前的区别和更新【转】
- 信1705-2 软工作业最大重复词查询思路: (1)将文章(一个字符串存储)按空格进行拆分(split)后,存储到一个字符串(单词)数组中。 (2)定义一个Map,key是字符串类型,保存单词;value是数字类型,保存该单词出现的次数。 (3)遍历(1)中得到的字符串数组,对于每一个单词,考察Map的key中是否出现过该单词,如果没出现过,map中增加一个元素,key为该单词,value为1(
- iOS10 CAAnimationDelegate 的简单适配
- centos 配置subversion svn
- linux通配符,grep和 egrep区别
- Kubernetes1.1源码分析(二)
- Linux之CentOS7.5安装及克隆
- jQuery实现高亮显示网页关键词的方法