题解 P3545 【[POI2012]HUR-Warehouse Store】

唯爱你一生 · 2018-08-28 12:31:28 · 题解

C++题解 //样例貌似没过，但神奇的AC了 这一题是一道很明显的贪心 用优先队列写非常方便 还有就是一定要开long long int 我开始就是被坑了导致80分 直接上代码

#include<iostream>
#include<queue>
#include<algorithm>//头文件。其实可以用bits的 
using namespace std;
long long int ans[300006],cnt=0,tot=0,sum=0;//注意：这里一定要开long long int，不然会错 
struct Day{
    long long int a;
    long long int b;
}day[300006];//定义结构体天数
struct Point{
    long long int g;
    long long int p;
    Point(long long int c,long long int d){
        g=c;p=d;
    }//结构体函数 
};//结构体 
struct Rule{     
    bool operator()(const Point &a,const Point &b){
        return a.g<b.g;
    }
};//结构体
priority_queue<Point,vector<Point>,Rule>a;//优先队列，个人认为这样写很方便 
int main(){
    std::ios::sync_with_stdio(false);//对cin的读入优化 
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>day[i].a;
    for(int i=1;i<=n;i++)
        cin>>day[i].b; 
    for(long long int i=1;i<=n;i++){
        tot+=day[i].a;
        if(tot>=day[i].b){
            tot-=day[i].b;
            a.push(Point(day[i].b,i));
            sum++;
        }
        else{
            if(!a.empty()&&a.top().g>day[i].b){
                tot+=a.top().g;
                tot-=day[i].b;
                a.pop();
                a.push(Point(day[i].b,i));
            }
        }
    }//贪心 
    while(!a.empty()){
        ans[++cnt]=a.top().p;
        a.pop();
    }
    sort(ans+1,ans+cnt+1);//这里要对ans数组进行排序 
    cout<<sum<<endl;//输出sum的值 
    for(int i=1;i<=cnt;i++) 
        cout<<ans[i]<<" ";
    //输出ans 
    return 0;//结束主程序 
}