常州Day4(补8.15）

上午老师让我们把前几天的东西消化掉,我利用这时间改掉了昨天的T1

一种朴素的做法，用f[i]表示存留区间内（[1,i]）没有其他合并时的贡献
比赛时就只想到这，但这样无法处理有包含关系的区间，想不出怎么解决就先这么打上去了想着碰碰运气（什
赛后看题解才知道，要将每个牌组按数量从小到大排序，从小到大合并，如果存在包含关系的区间考虑更新f

#include
using namespace std;
#define PII pair
const int N=3005;
int n,a[N<<1],f[N<<1],g[N<<1];
/*g[i]表示将a[i]合并所得的最大得分*/
vector  p(N);
vector  pp(N);
/*p[i]存i在n张牌中的起始位置和终止位置
pp同p,按照两张牌间隔距离进行排序*/
bool cmp(PII a,PII b){
    return a.second-a.first>n;
    for(int i=1;i>a[i];
        if(p[a[i]].first)p[a[i]].second=i;
        else p[a[i]].first=i;
    }
    p.push_back({0,2*n+1});//用于最后得出整个区间的值
    pp=p;
    sort(pp.begin(),pp.end(),cmp);
    for(int i=1;i<pp.size();i++){//区间从小到大合并
        PII tmp=pp[i];
        int l=tmp.first,r=tmp.second;
        f[l]=a[l];
        for(int j=l+1;jl){
                f[j]=max(f[j],f[b-1]+g[j]);
            }
        }
        g[r]=f[r];
    }
    cout<<g[n*2+1]<<endl;
    return 0;
}

下午是二分答案
例1晒衣服
可以贪心地每次烘干最湿的衣服
用到优先队列来存各个湿度

#include
using namespace std;
const int N=5e5+5;
int n,a,b,w[N],d;
struct cmp{
    bool operator()(const int &a,const int &b){
        return a<b;
    }
};
priority_queue <int,vector,cmp> q;
int main(){
    cin>>n>>a>>b;
    for(int i=1;i>w[i];
        q.push(w[i]);
    }
    while(q.top()>d*a){
        d++;
        int tmp=q.top();
        q.pop();
        tmp-=b;
        q.push(tmp);
    }
    cout<<d; 
    return 0;
} 

先二分一个答案mid，然后枚举每件衣服，若湿度小于等于天数乘自然晒干速度，则表示第i件衣服可以自然晒干，否则表示需要用上 二者之差除以烘干速度 个单位时间的烘衣机，累计烘衣机所用的时间，若小于等于天数，则表示该答案可行，更新答案，并继续在[L,mid-1]内进行二分答案，否则该答案不可行，继续在[mid+1,R]内进行二分答案

#include
using namespace std;
const int N=5e5+5;
int n,a,b,w[N];
int main(){
    cin>>n>>a>>b;
    for(int i=1;i>w[i];
    }
    int l=1,r=N,mid=(l+r)>>1,ans;
    while(l>1;
        for(int i=1;imid*a){
                t+=ceil(double(w[i]-mid*a)/double(b));
            }
        }
        if(mid<t)l=mid+1;
        else{
            r=mid;
            ans=mid;
        }
    }
    cout<<ans<<endl;
    return 0;
}