(C++)2000年某竞全国赛第二题C++解法
phpskycn2009/08/29软件综合 IP:天津
题目是某BLOG上转来的,解法
一幢33层的大楼有一部电梯停在第一层,它一次最多能容纳32人,而且只能在第2层至第33层中的某一层停一次,对于每个人来说,他往下走一层楼梯感到1分不满意,往上走一层楼梯感到3分不满意,现在有32个人在第一层,并且他们分别住在第2至33层的每一层,问:电梯停在那一层,可以使得这32个人不满意的总分达到最小?最小值是多少?(有些人可以不乘电梯而直接从楼梯上楼)2000年全国竞赛第二试最后一题。
C++ Code
Point cache;
Point  f(int x){
pt.x  = x;
pt.y = (33-x)*(x+1+33)/2+3*(x-2)*(x-1+2);
return pt;
}
Point GMV(NULL){
Point pt;
while((pt.x<33)){
pt.x++;
Point p = f(x);
if(p.x > cache.x){
cache.x = p.x;}
}
return cache;
}
// endl
说明:执行GMV(),cache.x是求得的层数,cache.y是不满度的最小值。
算法很简单。
+200  科创币    虎哥    2009/08/29 代码是原创吗?
+50  科创币    1989sean    2013/03/09 今天的分数全都给你.
来自:计算机科学 / 软件综合
24
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
phpskycn 作者
15年5个月前 IP:未同步
147564
顶起
这个贴子怎么没人回?
“学术价值”比较高
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
phpskycn作者
15年5个月前 IP:未同步
147719
回答虎哥:
是原创的
代码是用手机打的,还没机会测试……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
phpskycn作者
15年5个月前 IP:未同步
148056
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
phpskycn作者
15年5个月前 IP:未同步
148076
终于有人看出来了
估计怪叔叔没看
但是6楼的算法不对
“首项+末项的和乘以项数除以二”
求要往下走的不满意度
(1+33)*(33-x-1)/2
求要往上走的不满意度
(x-2)*(1+x-2)*3/2
所以
pt.y=(1+33)*(33-x-1)/2+(x-2)*(1+x-2)*3/2
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
phpskycn作者
15年5个月前 IP:未同步
148092
我怎么好像记得答案是7?!
可能搞错了,那次数学课我在睡觉
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
phpskycn作者
15年5个月前 IP:未同步
148150
转自我的Blog
正确解法
思路:首先定义一个函数f()计算不满意度的和,为了方便后面的计算,该函数的返回值类型为Point类型。后面再计算1<x<34时对应的y值,另外还需要一个Point类型的全局变量cache,作为数据缓冲。之后,对比计算得到的y值,如果比cache.y小,就写入cache。
C++ Code
Point cache;
Point f(Point pt){
Point p;
int x = pt.x;
p.x = pt.x;
p.y = (1+33)*(33-x-1)/2+(x-2)*(1+x-2)*3/2;return p;}
Point GMinV(){
Point p;
Point p1;
p.x = 0;
while((p.x)<34)
{p.x ++p1.y = f(p);
if(p1.y<cache.y){cache.x = p.x;cache.y = p1.y;}}
return cache;}
//cache.y是不满度的最小值,cache.x是此时电梯停的楼层。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
phpskycn作者
15年5个月前 IP:未同步
148184
很明显是25
Noname怎么得到27的?
算了,此贴的是是非非,等我下个月回杭州再说
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

所属专业
上级专业
同级专业
phpskycn
专家 老干部 学者 机友 笔友
文章
402
回复
4591
学术分
8
2009/03/15注册,2个月6天前活动

CV

主体类型:个人
所属领域:无
认证方式:手机号
IP归属地:未同步
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}