最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 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. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

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

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级