6 solutions

  • 0
    @ 2021-10-14 20:36:14

    这里用了一个对组存了一下每个任务的结束时间以及未完成会扣除的钱,要使扣除的钱最少,就必须得优先完成权重大的任务,我的思路是使用一个布尔数组来表示这一天有没有被使用,比如一个任务截止为4,那我就可以使用4之前的任意一天来完成,但是这里注意,**我完成的时候必须从截止日期的那一天开始找,往回找,比如第4天截止,我就要先判断第4天,再判断第三天,不然后面可能会因为存在比如如果我在第四天完成了截止日期为4的任务,那么紧跟着的截止日期为1的任务就还有完成的机会,如果我截止日期为第四天,我却选择第一天来完成,那么我截止日期为1并且权重仅仅小于截止日期为4的任务就无法完成。**如果这个任务没有找到能用来完成的日期,那我就只能将金额扣除 下面还是贴一下代码:

    #include <bits/stdc++.h>
    using namespace std;
    bool judge [505];
    pair<int,int>pa[505];
    bool cmp(pair<int,int>a,pair<int,int>b)
    {
    	return a.second>b.second;
    }
    int main()
    {
    	int m,n;
    	cin>>m>>n;
    	for(int i=1;i<=n;++i)cin>>pa[i].first;
    	for(int i=1;i<=n;++i)cin>>pa[i].second;
    	sort(pa+1,pa+n+1,cmp);
    	for(int i=1;i<=n;++i)
    	{
    		for(int j=pa[i].first;j>=1;j--)
    		{
    			if(judge[j]==false)
    			{
    				judge[j]=true;
    				break;
    			}
    			if(j==1){
    			m-=pa[i].second;
    			break;}
    		}
    	}
    	cout << m << endl;
    }
    

    Information

    ID
    94
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    3
    Tags
    # Submissions
    94
    Accepted
    51
    Uploaded By