「日常训练」Woodcutters(Codeforces Round 303 Div.2 C)
2024-10-07 18:40:33
这题惨遭被卡。。卡了一个小时,太真实了。
题意与分析 (Codeforces 545C)
题意:给定\(n\)棵树,在\(x\)位置,高为\(h\),然后可以左倒右倒,然后倒下去会占据\([x-h,x]\)或者\([x,x+h]\)区间,如果不砍伐,占据\([x,x]\)区域。
问你最多砍多少棵树,砍树的条件是倒下去后占有的区间不能被其他树占据。
分析:在这条题目的条件下,这是一个傻逼贪心题。(然后我读错两次题目,怎么也想不出来贪心策略。。。。)
很简单的策略:能往左倒往左倒,能往右倒往右倒。因为树的倒下无论如何只会影响额外的一棵树!!(换句话说,如果说倒下的区间不用考虑树的存在,就很有意思了)举个例子,考虑一种极端情况:第\(i\)棵树到第\(n\)棵树如果挨个往左倒正好完美覆盖。那么这种情况下你第\(i-1\)棵树如果可以往右倒照样可以往右倒,因为每棵树的倒下只影响另外左右一个树,那么我大不了第\(i\)棵树不倒,我的答案不会更差。这样就确定了贪心策略的正确性。
代码
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define ZERO(x) memset((x), 0, sizeof(x))
#define ALL(x) (x).begin(),(x).end()
#define rep(i, a, b) for (repType i = (a); i <= (b); ++i)
#define per(i, a, b) for (repType i = (a); i >= (b); --i)
#define QUICKIO \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
using namespace std;
using ll=long long;
using repType=int;
int main()
{
int n; cin>>n;
pair<int,int> tree[100005];
rep(i,1,n) cin>>tree[i].fi>>tree[i].se;
int cnt=0;
int npos=0,ntree=1;
int cut[100005]; ZERO(cut);
rep(i,1,n)
{
int l_boundary=tree[i].fi-tree[i].se,
r_boundary=tree[i].fi+tree[i].se;
bool lok=true;
per(j,i-1,1)
{
if(tree[j].fi>=l_boundary || (cut[j]==2&&tree[j].fi+tree[j].se>=l_boundary))
{
lok=false; break;
}
if(tree[j].fi+tree[j].se<l_boundary) break;
}
if(lok) { cut[i]=1; continue; }
bool rok=true;
rep(j,i+1,n)
{
if(tree[j].fi>r_boundary) break;
else if(tree[j].fi<=r_boundary) {rok=false; break;}
}
if(rok) cut[i]=2;
}
int ans=0;
rep(i,1,n) if(cut[i]) ans++;
cout<<ans<<endl;
return 0;
}
最新文章
- PHP面向对象(OOP)编程入门教程
- 【ASP.NET Identity系列教程(二)】运用ASP.NET Identity
- JavaScript实现li隔行变色
- [BZOJ2790][Poi2012]Distance
- IBM HTTP Server Performance Tuning
- Linux基础01 学会使用命令帮助
- FZU 1753
- MySQL 数据表修复及数据恢复
- Picasso – Android系统的图片下载和缓存类库
- 那些学些网址_jquery初学知识
- vue结合axios使用入门
- linux 乌班图 lnmp环境搭建
- java版数据结构与算法第二章数组
- Android:ViewGroup和View的Touch事件
- 移动端滑动轮播,原生JS
- Some reading, some thinking.
- oracle 11gR2 ASM添加和删除磁盘
- js拾遗: replace 替换参数
- STM32cube库配置双ADC的同步规则采样
- JS倒计时、计时
热门文章
- Vue点击切换class
- Linux学习总结(四)-两种模式修复系统,单用户,救援模式
- [转]JOGL安装
- 【题解】洛谷P1879 [USACO06NOV] Corn Fields(状压DP)
- 锐捷交换机RG-3760-24 的简单配置与VLAN搭建
- c# 关闭socket的标准方法
- “->;”和“.”运算符
- 【JavaScript-基础-cookie从入门到进阶】
- 常见的springmvc、SpringBoot的注解
- Oracle在线重定义(online redefinition)--将普通表改为分区表