2017级算法模拟上机准备篇(贪心 进阶_1)

AlvinZH想回家

这道题本质上还是贪心与算法的简单的结合，有一个小的trick值的主要一下，结构体优先队列的运算符重载问题。

 bool operator<(const Flight& b) const {
        return c < b.c;
    }

对于每一步都需要当前最大值的问题，我们可以使用优先队列来辅助我们进行操作。

bool operator <(const Time& a,const Time& b){
    return a.start > b.start;
}  //这里以大于重载小于是因为默认情况下，优先队列是以大的作为队首，这样一反，就可以再默认情况下使得小的作为队首

struct Time{  
    int start, end;  
    bool operator < (const Time& t)const{  
        return start > t.start;  
    }  
};  

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxlen=500010;
//不能早于最早的开发时间 那只需要在每次预定的时间内 选择延迟费用最高的航班即可
struct flight{
    int c,id;
    bool operator < (const flight& b) const{
        return c < b.c;
    }
}ar[500005],t;
long long ans=0;
priority_queue<flight> q;

int main(){
    //每次都要取当前的最大值 要考虑到优先队列呀
    //结构体优先队列的操作符号的 重加载
    int n,i,j,k;
    while(~scanf("%d %d",&n,&k)){
        
        ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&ar[i].c);
            ar[i].id=i;
        }
        for(i=1;i<=k;i++)
            q.push(ar[i]);
        for(int i=k+1;i<=k+n;i++){
            if(i<=n)
                q.push(ar[i]);
            t=q.top();
            q.pop();
            ans += (long long)t.c * (i-t.id);
        }
        printf("%lld
",ans);
    }
    return 0;
}