这题惨遭被卡.. 卡了一个小时, 太真实了.
题意与分析 (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;
- }
来源: http://www.bubuko.com/infodetail-2788340.html