A Small Shop------贪心算法

第 188 题  ：  家庭作业
(时间限制为：1000毫秒)

 

问题描述

   Ignatius刚刚参见完第30节届ACM/ICPC比赛回到学校。现在他有很多的作业要做。每个老师都给了他一个完成作业的最后期限，如果他超过期限交作业，老师就会在他的期评中扣分。假设做每一门作业总是要一天。 Ignatius希望你能够帮助他安排做作业的一个顺序，以便能够被扣掉的分数最少。

输入：

   输入包含了多个测试用例。输入的第一行是一个整数T，代表测试用例的个数。接下来的就是T个测试用例的输入。每个测试用例都从一个正整数N(1<=N<=1000)开始，代表了作业的数目。接下来有2行。第一行包含N个整数，分别代表各个作业提交的最后期限；第二行也有N个整数，即对应于各个作业操过时间提交的扣分。

输出：

   对每一个测试用例，你应该输出：在一行中输出，最小的扣分数。

样例输入：
2
3
3 3 3
10 5 1
3
1 3 1
6 2 3

样例输出：

0

3

 

#include<iostream> using namespace std; typedef struct { int time; int w; }Node; Node h[1002]; Node d[1002]; bool flag[1002]; int lot=0; int n; int high; int findmax() { int i,max1=0,loc=-1; for(i=1;i<=n;i++) { if(flag[i]==0) { if(max1<h[i].w) { max1=h[i].w; loc=i; } } } return loc; } bool dowith(int now) { int i,sum=0; for(i=1;i<=lot;i++) { if(d[i].time<=h[now].time) sum++; } if(h[now].time>sum) { return true; } return false; } bool dowi(int now) { int i,sum=0; for(i=1;i<=lot;i++) { if(d[i].time<=d[now].time) sum++; } if(d[now].time>=sum) { return true; } return false; } void deal() { int i,now,j; for(i=1;i<=n;i++) { now=findmax(); flag[now]=1; if(now==-1)return; if(!dowith(now))continue; d[++lot]=h[now]; for(j=1;j<=lot;j++) { if(d[j].time>h[now].time) { if(!dowi(j)) { lot--; break; } } } } } int main() { int t,i,s; cin>>t; while(t--) { lot=0; high=-1; s=0; memset(flag,0,sizeof(flag)); cin>>n; for(i=1;i<=n;i++) { cin>>h[i].time; if(high<h[i].time) { high=h[i].time; } } for(i=1;i<=n;i++) { cin>>h[i].w; s+=h[i].w; } deal(); for(i=1;i<=lot;i++) { // cout<<d[i].time<<" "<<d[i].w<<" "; s-=d[i].w; } cout<<s<<endl; } return 0; }