【CodeForces】913 D. Too Easy Problems

【题目】D. Too Easy Problems

【题意】给定n个问题和总时限T，每个问题给定时间ti和限制ai，当解决的问题数k<=ai时问题有效，求在时限T内选择一些问题解决的最大有效问题数。n<=2*10^5，T<=10^9。

【算法】贪心（排序+堆）

【题解】因为T太大，不能考虑背包。

容易发现k越小越能使更多问题有效，所以一定有最优方案的所有问题均有效。

当k唯一确定时，其实就是在所有ai>=k的问题中选取时间最少的几个解决。

当k减小时，选择的范围扩大，就可以选择一些时间更少的替换掉已选问题中时间最长的，这显然可以用堆维护。

所以得到做法——按k从大到小排序，然后依次扫描，维护一个时间大顶堆，每次：

1.若当前k>size（堆大小），弹出堆顶至size=k。

2.若堆中可以直接加入当前问题（k<size和满足时限），则直接加入。

3.否则考虑是否可以替换堆顶，可以则替换。

每次统计答案，找到最大值。

观察三个操作，容易发现当出现k>size的情况后，答案不可能再变大，也就是答案是一个凸函数，顶点出现在k>size时。

所以只需要再k>size输出当前堆中元素即是答案。

复杂度O(n log n)。

#include<cstdio>

#include<cctype>

#include<queue>

#include<algorithm>

using namespace std;

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int inf=0x3f3f3f3f,maxn=;

int n;

struct cyc{

    int k,t,id;

}a[maxn];

struct node{

    int id,t;

    bool operator < (const node &a)const{

        return t<a.t;

    }

};

priority_queue<node>Q;

bool cmp(cyc a,cyc b){return a.k>b.k;}

int T;

int main(){

    n=read();T=read();

    for(int i=;i<=n;i++)a[i].k=read(),a[i].t=read(),a[i].id=i;

    sort(a+,a+n+,cmp);

    int size=,time=;

    for(int i=;i<=n;i++){

        if(size>a[i].k){printf("%d\n%d\n",size,size);while(!Q.empty())printf("%d ",Q.top().id),Q.pop();return ;}

        if(size<a[i].k&&time+a[i].t<=T)Q.push((node){a[i].id,a[i].t}),size++,time+=a[i].t;

        else if(!Q.empty()&&a[i].t<Q.top().t){time-=Q.top().t;Q.pop();Q.push((node){a[i].id,a[i].t});time+=a[i].t;}

    }

    printf("%d\n%d\n",size,size);while(!Q.empty())printf("%d ",Q.top().id),Q.pop();return ;

}

巴特西

【CodeForces】913 D. Too Easy Problems

最新文章

热门文章