LOJ P10004 智力大冲浪题解

程序员玉宽技术 2022年11月23日

0 收藏 905 点赞 4,941 浏览 919 个字

每日一题 day37 打卡

Analysis

经典的带限期和罚款的单位时间任务调度问题

将 val 从大到小排序，优先处理罚款多的，将任务尽量安排在期限之前，并且靠后，如果找不到，则放在最后面

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #define int long long
 #define maxn 500+10
 #define rep(i,s,e) for(register int i=s;i<=e;++i)
 #define dwn(i,s,e) for(register int i=s;i>=e;--i)
 using namespace std;
 inline int read()
 {
     int x=;
     bool f=;
     char c=getchar();
     for(; !isdigit(c); c=getchar()) if(c=='-') f=;
     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
     if(f) return x;
     return -x;
 }
 inline void write(int x)
 {
     if(x<){putchar('-');x=-x;}
     if(x>)write(x/);
     putchar(x%+'');
 }
 int m,n,sum;
 struct node
 {
     int tim,_val;
 }x[maxn];
 int book[maxn];
 bool cmp(node x,node y)
 {
     return x._val>y._val;
 }
 signed main()
 {
     m=read();n=read();
     rep(i,,n) x[i].tim=read();
     rep(i,,n) x[i]._val=read();
     sort(x+,x+n+,cmp);
     rep(i,,n)
     {
         int flag=;
         dwn(j,x[i].tim,)
             if(book[j]==)
             {
                 book[j]=;
                 flag=;
                 break;
             }
         if(flag==)
         {
             dwn(j,n,)
                 if(book[j]==)
                 {
                     book[j]=;
                     break;
                 }
             sum+=x[i]._val;
         }
     }
     write(m-sum);
     return ;
 }