贪心--upc赶作业贪心

问题 : 【贪心】赶作业时间限制: 1 Sec 内存限制: 64 MB
提交: 100 解决: 65
[ 提交][ 状态][ 讨论版] 题目描述小墨老师总是不及时做作业，所以他总有很多的作业要做。每个老师都给了他一个完成作业的最后期限，如果他超过期限交作业，老师就会在他的期末评价中扣分。假设做每一门作业总是要一天。小墨老师希望你能够帮助他安排做作业的一个顺序，以便能够被扣掉的分数最少。输入输入包含了多个测试用例。输入的第一行是一个整数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

【贪心--upc赶作业】开始刷贪心的例题，结果第一道题就摔了跟头，受HDU中“今年暑假不AC”题的影响，这道题未认真思考，想当然的就将时间排序，结果就是一个WA。认真思考后，正确的贪心策略应该是先考虑扣分最多的作业，从截止的那天开始安排，若已安排其他的作业则继续向前安排，成功AC。

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define INF 0x3f3f3f3f using namespace std; struct node { int t,s; }; int cmp(node a,node b) { return a.s>b.s; } int vis[100005]; int main() { int t; while(~scanf("%d",&t)) while(t--) { memset(vis,0,sizeof(vis)); int n; scanf("%d",&n); node p[1005]; for(int i=1; i<=n; i++) scanf("%d",&p[i].t); for(int i=1; i<=n; i++) scanf("%d",&p[i].s); sort(p+1,p+n+1,cmp); int ans=0; for(int i=1; i<=n; i++) { int tt=p[i].t; while(tt) if(vis[tt]==0) { vis[tt]=1; break; } else if(tt==1) ans+=p[i].s,tt--; else tt--; } printf("%d\n",ans); } return 0; }