题意:
有n个作业(1<=n<=1000),每个作业都有自己的DDL与平时分。请安排做作业的顺序,拿到最多的平时分。
输入:共T个测试样例,每个测试样例共三行,第一行为作业数量n,第二行n个数表示DDL,第三行n个数表示平时分。
思路:
对DDL进行降序排序。从最后一天往前,给每一天安排要写的作业。枚举到第i天时,将所有DDL=i的作业加入大根堆,然后从大根堆里选出平时分最大的作业安排在当天。
总结:
一道贪心题,应想到该O(nlogn)的算法。
大根堆使用了priority_queue,要求大根堆用到的排序cmp应新在一个struct里重载(),而且大根堆对应a<b。使用与学过的大根堆使用方法相同,q.push(x),q.top(),q.pop()等。
代码:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct homework
{
int ddl;
int score;
};
struct cmp
{
bool operator() (const homework&a,const homework&b)
{
return a.score<b.score;
}
};
bool cmp1(const homework&a,const homework&b)
{
return a.ddl>b.ddl;
}
int main()
{
int t;
cin>>t;
for(int t1=0; t1<t; t1++)
{
int n;
cin>>n;
homework *hw=new homework[n];
for(int i=0; i<n; i++)
cin>>hw[i].ddl;
for(int i=0; i<n; i++)
cin>>hw[i].score;
sort(hw,hw+n,cmp1);
priority_queue<homework,vector<homework>,cmp> q;
int sum=0;
int index=0;
int lastddl=hw[0].ddl;
for(int i=lastddl; i>=1; i--)
{
if(index<n)
while(hw[index].ddl==i)
{
q.push(hw[index]);
index++;
if(index>=n) break;
}
if(!q.empty())
{
homework maxhw=q.top();
q.pop();
sum+=maxhw.score;
}
}
int ans=0;
for(int i=0; i<n; i++)
ans+=hw[i].score;
ans=ans-sum;
cout<<ans<<endl;
while(!q.empty())
q.pop();
delete []hw;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)