BZOJ 3613 HEOI 2014 南园满地堆轻絮 二分+贪心
发布时间：2020-12-13 20:16:47 所属栏目：PHP教程 来源：网络整理
导读：题目大意 给出1个数字序列，要求将这个数字序列变成单调不降的序列。若原来的数字是A[i],变化以后的数字是B[i],那末花费是 | A [ i ] ? B [ i ] | 。求出1种方案，使得最大的花费最
题目大意给出1个数字序列，要求将这个数字序列变成单调不降的序列。若原来的数字是A[i],变化以后的数字是B[i],那末花费是 思路1眼就可以看出是2分，然后贪心甚么的随意yy1下就好了。 CODE#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 50010
using namespace std;
#define LEFT (pos << 1)
#define RIGHT (pos << 1|1)
struct Cow{
int x,y,c;
int st,ed;
bool operator <(const Cow &a)const {
return y > a.y;
}
void Read() {
scanf("%d%d%d",&x,&y,&c);
x *= -1;
st = c * (x - 1);
ed = st + (c << 1);
}
}src[MAX];
int cows;
pair<int,int *> xx[MAX << 1];
int cnt,t;
int tree[MAX << 4];
inline void PushDown(int pos)
{
if(tree[pos]) {
tree[LEFT] = tree[pos];
tree[RIGHT] = tree[pos];
tree[pos] = 0;
}
}
void Modify(int l,int r,int x,int y,int c,int pos)
{
if(l == x && y == r) {
tree[pos] = c;
return ;
}
PushDown(pos);
int mid = (l + r) >> 1;
if(y <= mid) Modify(l,mid,x,c,LEFT);
else if(x > mid) Modify(mid + 1,r,RIGHT);
else {
Modify(l,LEFT);
Modify(mid + 1,mid + 1,RIGHT);
}
}
inline int Ask(int l,int pos)
{
if(l == r) return tree[pos];
PushDown(pos);
int mid = (l + r) >> 1;
if(x <= mid) return Ask(l,LEFT);
return Ask(mid + 1,RIGHT);
}
bool v[MAX];
int main()
{
cin >> cows;
for(int i = 1; i <= cows; ++i)
src[i].Read();
sort(src + 1,src + cows + 1);
for(int i = 1; i <= cows; ++i) {
xx[++cnt] = make_pair(src[i].st,&src[i].st);
xx[++cnt] = make_pair(src[i].ed,&src[i].ed);
}
sort(xx + 1,xx + cnt + 1);
for(int i = 1; i <= cnt; ++i) {
if(i == 1 || xx[i].first != xx[i - 1].first)
++t;
*xx[i].second = t;
}
for(int i = 1; i <= cows; ++i)
Modify(1,cnt,src[i].st,src[i].ed,i,1);
for(int i = 1; i <= cnt; ++i)
v[Ask(1,1)] = true;
int ans = 0;
for(int i = 1; i <= cows; ++i)
ans += v[i];
cout << ans << endl;
return 0;
}（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |