俄罗斯ITMO大学的算法
team1025 2015-05-10 12:21:58
地址在http://neerc.ifmo.ru/trains/peking/problems-2B.pdf 第一题。 我觉得group training的时间只要枚举pi/si就行了,再加上一个0. group training的时间必定在这些值之中。证明如下: 首先可以知道值必定在0-最大的pi/si之间,然后对于任意大小相邻的pi/si和pj/sj,group training在这两个值之间取值的时候必定是单调的,这点可以根据计算总花费的公式可以看出来,设group training的值为x,则总花费是b*x+(所有pi/si>x的人中,a*(pi-x*si)/qi=>a*pi/qi-x*si/qi*a),x改变时,x乘的si/qi都相同,因为在设定的区间中,pi/si>x的人时固定的,很明显此时求总花费的公式是单调的,因此最值在端点处取得。总共有n个这样的区间,因为要把0也算进去,这样就可以枚举pi/si再加上一个0处的值,比较可得最小花费了。我不知道我这样做哪里有问题,反正第6个答案错了。。。求指导。。。