题面

<center>2058: [CTSC2007]挂缀pendant<center>
<center>时间限制:40秒 内存限制:162MB <center>

题目描述
  “珠缀花蕊,人间几多酸泪”…… 挂缀在很早就被人们作为一种装饰品,垂坠的风韵,华丽摇曳的摆动,展现出一种与众不同的优雅与高贵。而我们的主人公小Q,正想买一条漂亮的挂缀放在寝室里作为装饰。挂坠的构成,是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成:分别是珠子、珠子上方的连接环与珠子下方的挂钩。我们可以简单的认为从上往下数的第i个缀珠是将它的连接环套在其上方(也就是第i-1个)缀珠的挂钩之上(第一个除外)。小Q想买一根足够长的挂缀,这样显得更有韵味? 然而商店的老板告诉小Q,挂缀是不可能做到任意长的,因为每一个珠子都受到重力作用,对其上方的挂钩有一定的拉力,而挂钩的承受能力是有限的。老板还告诉小Q,他一共拥有N个珠缀(假设每一个珠缀都很漂亮,小Q都很喜欢),每个珠缀都有其各自的重量与承受能力。一个挂缀是稳定的,当且仅当对于其上的每一个珠缀,它下方所有珠缀的重量和(不包含自身)不超过其挂钩的承受能力。小Q希望她的挂缀尽量长,你能帮她计算出最长可能的稳定挂缀么?当然,如果有多个可选方案,小Q希望总重量最小的。
输入
   第一行包含一个正整数N,表示商店拥有的珠缀数目。接下来N行,每行两个整数(C$_i$,W$_i$),分别表示第i个珠缀的承受能力与重量。
输出
  包行两行。第一行包含一个整数L,表示可以找到的最长稳定挂缀长度。第二行包含一个整数W,表示可以找到的长度为L的稳定挂缀中的最小重量和。
样例输入

4
3 5
5 1
3 2
4 6

样例输出

3
8

思路

题解
  贪心题,应该把自身质量小的珠缀放在下面,因为越往下需要承受该珠缀的挂钩越多,另外承重能力强的珠缀应该放在上面,所以最终的挂坠序列从上到下应该是按照(C$_i$+W$_i$)递减的顺序排列的。说明如下:考虑最终序列上的n$_i$和n$_{i+1}$: 看是否可以可以交换这两个珠缀的顺序:应该保证到n$_{i+1}$时,整个挂坠的承重能力越大越好,而整个挂坠的承重能力取决于(n+1)个挂钩中此时剩余承重能力最小的挂钩,n$_i$和n$_{i+1}$的顺序不会对1~n-1的挂钩剩余承重能力产生影响,只需要考虑,取第n个和第n+1个挂钩的剩余承重能力的最小值更大:
  1.顺序为,n$_i$和n$_{i+1}$时,……=min{C$_i$-W$_{i+1}$,C$_{i+1}$}
  2.顺序为,n$_i$和n$_{i+1}$时,……=min{C$_{i+1}$-W$_i$,C$_i$}
  (1)C$_i$-W$_{i+1}$>C$_{i+1}$,取C$_{i+1}$,此时C$_i$>C$_{i+1}$+W$_{i+1}$,那么,C$_i$>C$_{i+1}$-W$_i$,下式必定取C$_{i+1}$-W$_i$;则顺序为‘1.’时,剩余承重能力更大,且必有:C$_i$+W$_i$>C$_{i+1}$+W$_{i+1}$
  (2)C$_i$-W$_{i+1}$<C$_{i+1}$,取C$_i$-W$_{i+1}$,若C$_{i+1}$-W$_i$>C$_i$,取C$_i$,则顺序为‘2.’时,剩余承重能力更大,C$_{i+1}$>C$_i$+W$_i$,交换顺序后,仍然满足C$_i$+W$_i$>C$_{i+1}$+W$_{i+1}$
  (3)C$_i$-W$_{i+1}$<C$_{i+1}$,取C$_i$-W$_{i+1}$,若C$_{i+1}$-W$_i$<C$_i$,取C$_{i+1}$-W$_i$,只有C$_i$-W$_{i+1}$>C$_{i+1}$-W$_i$即C$_i$+W$_i$>C$_{i+1}$+W$_{i+1}$时,才取顺序1.;否则交换顺序,仍然有C$_i$+W$_i$>C$_{i+1}$+W$_{i+1}$
  所以,最终证得:最后得挂坠序列中,必有C$_i$+W$_i$>C$_{i+1}$+W$_{i+1}$,由于i的随意性,则:所以最终的挂坠序列从上到下应该是按照(C$_i$+W$_i$)递减的顺序排列的。
  所以,最终求解方法:反向排序后,进行遍历即可,若符合承重能力,直接挂;否则看是否可以换,换的话,在满足符合承重能力的前提下,还要满足换的的珠缀质量,小于被换的。
  

源码

#include<iostream>
#include<algorithm>
#include<queue>
typedef long long ll;
const int N=2e5+5;
using namespace std;
typedef struct {//定义挂坠结构类型
    ll c,w;
}Node;
Node a[N];
inline bool cmp(Node a,Node b){//定义比较规则
    return a.c+a.w<b.c+b.w;
}
priority_queue<int>q;//优先队列,每次弹出max
ll n,sum=0,ans=0;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i){//输入数据
        cin>>a[i].c;
        cin>>a[i].w;
    }
    sort(a+1,a+n+1,cmp);//排序
    for (int i=1;i<=n;++i){//处理
        if (sum<=a[i].c){//加入挂坠的承受能力大于sum,则可以添加
            q.push(a[i].w);
            //更新sum,ans
            sum+=a[i].w;
            ans++;
        }
        else{//否则不能添加,进行更换
            if (sum-q.top()<=a[i].c && q.top()>a[i].w){
                //加入挂坠的承受能力大于取下挂坠后的sum,并且取下的挂坠重量大于加入的则可以更换
                sum+=a[i].w-q.top();//更新sum
                //更新挂坠队列
                q.pop();
                q.push(a[i].w);
            }
        }
    }
    cout<<ans<<'\n'<<sum<<'\n';//输出结果
}
/*
4
3 5
5 1
3 2
4 6
*/
Last modification:October 19th, 2019 at 10:18 pm
如果觉得我的文章对你有用,请随意赞赏