[牛客算法周周练7 ]C题O(nlogn)做法

A和E是签到题，就不写题解了。这里写一个C的贪心做法：
（要用到面向对象的思路）
首先预处理将所有的1连续段设置成一个类（结构体），这个结构体有连续段长度、中间的休息时间两个变量。很明显，对于给定的连续的‘1’，最终的最优工作方式是尽量平均的分配。例如，总共10天连续工作，若安排2天休息，那么一定是 3+（1）+3+（1）+2这样安排比较好。给定了以上两个变量的类，可以O(1)计算出最大连续时间、以及最优总消耗。
那么这道题就很简单了，开一个优先队列，每次“最大连续时间”的对象出队，给它添加一个新的休息时间即可。（最初所有连续段的休息时间都是0）
ac代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int len,kong;
    void judge(){
        cout<<this->len<<" "<<this->kong<<endl;
    }
    node(int len,int kong){
        this->len=len;
        this->kong=kong;
    }
    int getDx(){
        return (len+1)/(kong+1)+((len+1)%(kong+1)!=0)-1;
    }
    int getValue(){
        int ma=this->getDx();
        int cnt=kong+ma*(kong+1)-len;
        return cnt*(ma-1)*ma/2+(kong+1-cnt)*(ma+1)*ma/2;
    }
};
struct cmp{
    bool operator()(node a,node b){
        return a.getDx()<b.getDx();
    }
};
int main(){
   // node tt(2,1);
   // cout<<tt.getDx()<<" "<<tt.getValue();

    int n,i,j,k;
    cin>>n>>k;
    string s;
    cin>>s;
    vector<int>v;
    priority_queue<node,vector<node>,cmp>q;
    int cnt=0,sum=0,res=0;
    for(i=0;i<n;i++){
        if(s[i]=='1'){
            cnt++;
        }
        else{
            node temp(cnt,0);
            q.push(temp);
            sum+=temp.getValue();
            res+=cnt;
            cnt=0;
        }
    }
    if(cnt){
        node temp(cnt,0);
        q.push(temp);
        res+=cnt;
        sum+=temp.getValue();
    }
   // cout<<sum<<" "<<k<<" "<<res<<endl;
    while(sum>k){
        node temp=q.top();
        //temp.judge();
        q.pop();
        sum-=temp.getValue();
        node temp2(temp.len,temp.kong+1);
        sum+=temp2.getValue();
       // cout<<sum<<endl;
        q.push(temp2);
        res--;
    }
    //cout<<sum<<" "<<k<<" "<<res<<endl;
    cout<<res;

}