题意

（依然来自洛谷）

有C个奶牛去晒太阳 (1 <=C <= 2500)，每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值，太大就晒伤了，太小奶牛没感觉。

而刚开始的阳光的强度非常大，奶牛都承受不住，然后奶牛就得涂抹防晒霜，防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。

那么为了不让奶牛烫伤，又不会没有效果。

给出了L种防晒霜。每种的数量和固定的阳光强度也给出来了

每个奶牛只能抹一瓶防晒霜，最后问能够享受晒太阳的奶牛有几个。

分析

依然是一道贪心，依然是一道USACO的，依然是一道李煜东书上的，依然我是做不来的

对奶牛可承受的SPF（日光）最小值排序

对沐浴露（防晒霜？）最小值排序

证明过程略（哇，好懒）

Code

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

#define ll long long

#define N 50005

using namespace std;

int n,num;

struct COW {

    int l, r, id,ans;

    bool operator <(const COW x)

        const {

        return l < x.l;

    }

}cow[N];

int ans[N];

priority_queue<pair<int, int> > s;

int main()

{

    //freopen("testdata.in", "r", stdin);

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

    {

        cow[i].id = i;

        scanf("%d%d", &cow[i].l, &cow[i].r);

    }

    sort(cow + , cow +  + n);

    for (int i = ; i <= n; i++)

    {

        int total = s.size();

        if (total && -s.top().first < cow[i].l)

        {

            cow[i].ans = s.top().second;

            s.pop();

            s.push(make_pair(-cow[i].r, cow[i].ans));

            continue;

        }

        cow[i].ans = ++num;

        s.push(make_pair(-cow[i].r, num));

    }

    printf("%d\n",s.size());

    for (int i = ; i <= n; i++) ans[cow[i].id] = cow[i].ans;

    for (int i = ; i <= n; i++) printf("%d\n", ans[i]);

    return ;

}

巴特西

[POJ3614]Sunscreen (贪心)

题意

分析

Code

最新文章

热门文章