BZOJ 3613 HEOI 2014 南园满地堆轻絮二分+贪心

题目大意

给出1个数字序列，要求将这个数字序列变成单调不降的序列。若原来的数字是A[i],变化以后的数字是B[i],那末花费是|A[i]?B[i]| 。求出1种方案，使得最大的花费最小。

思路

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, y, c, LEFT);

    else if(x > mid) Modify(mid + 1, r, x, y, c, RIGHT);

    else {

        Modify(l, mid, x, mid, c, LEFT);

        Modify(mid + 1, r, mid + 1, y, c, RIGHT);

    }

}
inline int Ask(int l, int r, int x, int pos)

{

    if(l == r)  return tree[pos];

    PushDown(pos);

    int mid = (l + r) >> 1;

    if(x <= mid) return Ask(l, mid, x, LEFT);

    return Ask(mid + 1, r, x, 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, cnt, i, 1)] = true; int ans = 0; for(int i = 1; i <= cows; ++i) ans += v[i]; cout << ans << endl; return 0; }

数字

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

波比源码 » BZOJ 3613 HEOI 2014 南园满地堆轻絮二分+贪心

分享到：