首页 > 代码库 > codeforce 732D . Exams

codeforce 732D . Exams

2024-09-15 02:09:56   215人阅读

D . Exams

题意：一共有n天 m个考试 di表示第i天可以进行第m个考试 ai 表示第i个考试需要准备ai天才能通过考 问最少需要多少天才能通过所有考试

思路： 二分时间 每一次判断一下能否通过所有考试 得到最优解  每次二分到第x天时 从后面开始计算 尽量在后面的时间里考试 留更多的时间给前面的考试（比如第一次考试，如果可以在第5天和第7天考 如果第5天可以通过考试（即准备的时间大于等于ai），那么在第7天也一定可以通过，但是如果在第7天可以通过，在第5天不一定可以通过，所以一律选择时间靠后的那天进行考试）

AC代码：

#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
int n,m,a[100010],d[100010];
set<int> se;
bool solve(int mid){
    se.clear();
    for(int i=mid; i>=1; i--){
         if(d[i] && !se.count(d[i])){
             if(i>a[d[i]]){
               se.insert(d[i]);
             }
         }
    }
    return se.size()==m;
}
int main(){
    mem(a),mem(d);
    scanf("%d%d",&n,&m);
    int l=0,r=n,ans=0;
    for(int i=1; i<=n; ++i){
        scanf("%d",&d[i]);
    }
    for(int i=1; i<=m; ++i){
        scanf("%d",&a[i]);
        l+=a[i]+1;
    }
    while(l<=r){
        int mid=l+r>>1;
        if(solve(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans==0?-1:ans);
    return 0;
}

 

codeforce 732D . Exams


联系
我们