本文共 1332 字，大约阅读时间需要 4 分钟。

题意：有N个作业，每个作业都有一个t[i],s[i]分别表示ddl和超过ddl会扣除的分数，每天固定完成一个作业，求最合理的安排，使得被扣除的分数最少。输入T，表T个样例，每个样例首行为N，第二行为t[N]，第三行为s[N]。

原题链接：

分析：

一开始直觉是按ddl从小到大排序，然后依次完成每个作业，但并没有这么简单，卡在了题中第三个样例。正确的做法应该是： 1.将t[i]从小到大排序，t[i]相同则按s[i]从大到小排；

2.设time为写作业的第几天，当time<=t[i]时，说明能在ddl前完成，time++。而当time>t[i]时，说明超过了ddl了，此时，应该遍历s[0]~s[i-1]，若发现有s[k]<s[i]的，说明牺牲掉第k项作业来完成第i项作业，扣除的分数更少，这样安排更值得，否则，则直接弃掉作业i；

3.特别注意，超过ddl的数据要进行处理，否则可能会在后面的遍历操作中成了搅屎棍。 时间复杂度较大，但题中的数据较小，1<=N<=1000，解起来还是绰绰有余的。

伪代码如下：

输入T while(T- -) { int time,flag; long long min,score; 输出N； 输入t[N],s[N]; 排序； for(i=0;i<=n-1;i++) { if(time<=t[i]) time++; else { min=s[i];flag=i; for(j=0;j<i;j++) { if(min>s[j]){ min=s[j];flag=j;} } score+=min; s[flag]=inf; //注意！！！这一步很重要，将s[i]设为inf，表示已经超过ddl了 } 输出score; }

代码入下：

#include
   
    #define inf 100000000using namespace std;long long t[1005],s[1005];void sort(int n){	int i,j,k;	for(i=0;i<=n-2;i++)	{		k=i;		for(j=i+1;j<=n-1;j++)		    if(t[k]>t[j]) k=j;		    else if(t[k]==t[j])		    {		    	if(s[k]
    
     s[j])	    			{	    				min=s[j];	    				flag=j;					}				}				if(min!=s[i])				{					score+=min;					s[flag]=inf;				}				else				{					score+=min;					s[i]=inf;				}			}		}		printf("%lld\n",score);	}	return 0;}
    
   

Tips：其实解答过程中出现了一些困扰，担心会出现这样或那样的情况（具体忘了）而导致算法错误，但是，事实上不必过分的担忧的，因为到最后证明了出来，这些情况是不可能出现的。所以，如果下次再出现类似的担忧，不必慌，尝试证明这些搅屎棍是不可能出现的，成功了就继续，失败了就重来。

转载地址：http://dfdci.baihongyu.com/