注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

石门实验中学卢凯宾的博客

向前跑,迎着冷眼和嘲笑。

 
 
 

日志

 
 

推销员  

2015-12-13 12:08:03|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

推销员 - 卢凯宾 - 石门实验中学卢凯宾的博客

 

这道题一开始以为是dp,但似乎大家都是用贪心解决。事实上只要贪得正确,100分是没有问题的。

先用θ(n)找出最大值,然后,先根据推销疲劳值再根据距离进行排序,依次累加求和即可。
该算法的时间复杂度为θ(n+nlog2n)
# include <algorithm>
# include <cstdio>

const int SIZE = 100005;

struct Tnode {
	int S , A , sum ;
	void clear () {
		S = A = sum = -1 ;
	}
} a[SIZE];

int N , max_id , ans , distance ;

bool cmp ( Tnode , Tnode ) ;

int main () {
	freopen ( "salesman.in" , "r" , stdin ) ;
	freopen ( "salesman.out" , "w" , stdout ) ;
	scanf ( "%d" , &N ) ;
	for ( int i=0 ; i!=N ; ++i ) {
		scanf ( "%d" , &a[i].S ) ;
		a[i].S <<= 1 ;
	}
	max_id = N ;
	a[N].clear () ;
	for ( int i=0 ; i!=N ; ++i ) {
		scanf ( "%d" , &a[i].A ) ;
		a[i].sum = a[i].S + a[i].A ;
		if ( ( a[i].sum > a[max_id].sum ) || ( ( a[i].sum == a[max_id].sum ) && ( a[i].S > a[max_id].S ) ) ) {
			max_id = i ;
		}
	}
	ans = a[max_id].sum ;
	distance = a[max_id].S ;
	printf ( "%d\n" , ans ) ;
	a[max_id].clear () ;
	std::sort ( a , a + N , cmp ) ;
	for ( int i=0 ; i!=N-1 ; ++i ) {
		ans += a[i].A ;
		if ( a[i].S > distance ) {
			ans += ( a[i].S - distance ) ;
			distance = a[i].S ;
		}
		printf ( "%d\n" , ans ) ;
	}
	return 0 ;
}

bool cmp ( Tnode i , Tnode j ) {
	return ( ( i.A > j.A ) || ( ( i.A == j.A ) && ( i.S > j.S ) ) ) ;
}

  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018