Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:反例 1000/1000 , 100/200, 1/3 删掉一组

Posted by vrqq at 2018-06-17 23:23:14 on Problem 2976
In Reply To:贪心的能给出严格的证明吗? Posted by:nuanran at 2006-08-19 14:17:11
当然是删掉100/200了。问题在于:
我们假设k为答案
那么 (1000-1000k) + (100-200k) + (1-3k) = 0这个式子里面,看哪组<0且在k上升时候变化“最敏感”,显然是中间那组。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator