HDU 1789 Doing Homework again(贪心)

  在我上一篇说到的,就是这个,贪心的做法,对比一下就能发现,另一个的扣分会累加而且最后一定是把所有的作业都做了,而这个扣分是一次性的,所以应该是舍弃扣分小的,所以结构体排序后,往前选择一个损失最小的方案直接交换就可以了.

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
struct HomeWork
{
int deadline;
int reduce;
} hw[];
bool mark[];
int t;
int n;
int search(HomeWork a[],int x,int len)
{
int i,pl=-,min=x;
for(i=; i<len; i++)
if(mark[i]==true&&a[i].reduce<min)
{
min=a[i].reduce;
pl=i;
}
return pl;
}
bool cmp(HomeWork a ,HomeWork b)
{
if(a.deadline!=b.deadline)
return a.deadline<b.deadline;
else
return a.reduce>b.reduce;
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(mark,,sizeof(mark));
memset(hw,,sizeof(hw));
int i;
scanf("%d",&n);
for(i=; i<n; i++)
scanf("%d",&hw[i].deadline);
for(i=; i<n; i++)
scanf("%d",&hw[i].reduce);
sort(hw,hw+n,cmp); int day=,reduced=,tmp;
for(i=; i<n; i++)
{
if(day<hw[i].deadline)
{
day++;
mark[i] = true;
}
else
{
int ex = search(hw,hw[i].reduce,i);
if(ex!=-)
{
tmp=hw[ex].reduce;
hw[ex].reduce = hw[i].reduce;
hw[i].reduce=tmp;
}
reduced += hw[i].reduce;
}
} printf("%d\n",reduced); }
return ;
}
上一篇:Java I/O---概述


下一篇:SQL Server 2008 sp3启用1433端口的方法