首页 > ACM题库 > HDU-杭电 > HDU 1910 Loan Scheduling-贪心-[解题报告] C++
2013
12-23

HDU 1910 Loan Scheduling-贪心-[解题报告] C++

Loan Scheduling

没有任何难度的贪心。先按照时间预排序,对于每一新的任务,先判定是否还有处理的空间,如果没有就往前检索看看能不能够踢掉某些受益少的任务。

/*******************************************************************************
 # Author : Neo Fung
 # Email : [email protected]
 # Last modified: 2012-01-12 19:22
 # Filename: ZOJ3116 POJ3483 HDU1910 Loan Scheduling.cpp
 # Description : 
 ******************************************************************************/
#ifdef _MSC_VER
#define DEBUG
#endif

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
#define MAX 10010
using namespace std;

pair<int ,int> app[MAX];
bool used[MAX];

bool inline cmp(const pair<int,int> &lhs,const pair<int,int> &rhs)
{
	if(lhs.first==rhs.first)
		return lhs.second>rhs.second;
	else
		return lhs.first<rhs.first;
}

int main(void)
{
#ifdef DEBUG  
  freopen("../stdin.txt","r",stdin);
  freopen("../stdout.txt","w",stdout); 
#endif  
	int n,l;

	while(~scanf("%d%d",&n,&l))
	{
		for(int i=0;i<n;++i)
			scanf("%d%d",&app[i].second,&app[i].first);
		sort(app,app+n,cmp);
		memset(used,false,sizeof(used));

		int remain=l,now=0;
		int ans=0;
		for(int i=0;i<n;++i)
		{
			remain +=(app[i].first-now)*l;
			if(now<=app[i].first && remain)
			{
				--remain;
				ans+=app[i].second;
				used[i]=true;
			}
			else if(now<=app[i].first && !remain)
			{
				int t_ind=i;
				for(int j=i-1;j>=0;--j)
					if(used[j] && app[j].second<app[t_ind].second)
						t_ind=j;
				if(t_ind!=i)
				{
					used[t_ind]=false;
					ans-=app[t_ind].second;
					used[i]=true;
					ans+=app[i].second;
				}
			}
			now = app[i].first;
		}
		printf("%d\n",ans);
	}

  return 0;
}

解题报告转自:http://blog.csdn.net/neofung/article/details/7197183


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。