RQNOJ系统遇到了一个程序错误。

您可以通过邮件support (at) rqnoj.cn与我们进行联系。请附错误参考编号:298125

整数选择 - 题库 - RQNOJ
PID367 / 整数选择
题目描述

这是一个经典问题。原来的问题是关于树林中的树叶的,这里量化一下,改为整数选择问题。现有n个随机的正整数依次出现在你的面前。当每个数字出现时,你可以选择或放弃。一旦选择,不可更改;如果放弃,则不可返回重新选择。若前n-1个数均未选择,则必须选择第n个数。你的任务是,设计一种选择方案,使得在给定n的情况下,选择的数尽可能大。

我们提出这样一个较优的简单方案。可能存在较为复杂的方案使得选择到较大数的概率更大,但为了简化问题,我们只考虑以下方案中的“加权平均值”,即所有可能选择的数及其出现概率的乘积之和。

首先由n确定一个m。对前m个数,只记录其最大值max。对后n-m个数,若存在某数大于max,则选择此数。若前n-1个数均未选择,则选择第n个数。

你的程序需要计算出使得“加权平均值”最大的m。显然,0<=m<n。注意,n个数完全随机,可能重复,需要考虑所有情况下的概率。

输入格式

输入一行,一个整数n。数据范围:1<=n<=10000.

输出格式

输出一行,一个整数m。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论