顶起
这个贴子怎么没人回？
“学术价值”比较高
这个贴子怎么没人回？
“学术价值”比较高
19312
%7B%22isLastPage%22%3Atrue%2C%22notes%22%3A%5B%5D%2C%22pid%22%3A%22t19312%22%2C%22tid%22%3A%2219312%22%2C%22mainForumsId%22%3A%5B%22134%22%5D%2C%22categoriesId%22%3A%5B%220%22%5D%2C%22tcId%22%3A%5B%5D%7D
%7B%22isEditMode%22%3Afalse%7D
(C++)2000年某竞全国赛第二题C++解法
题目是某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是不满度的最小值。
算法很简单。
一幢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是不满度的最小值。
算法很简单。
引用第1楼phpskycn于2009-08-30 08:41发表的 :
顶起
这个贴子怎么没人回？
“学术价值”比较高
看不太懂，看来要借本C++研究一下算法
以前学VB都忽略了算法
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
回答虎哥：
是原创的
代码是用手机打的，还没机会测试……
是原创的
代码是用手机打的，还没机会测试……
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
不会C++...要是让本人用C编,我觉得还是可以编出来的...
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
这明明是纯粹的C嘛
LZ有几处错误
while((pt.x<33)){
pt.x++;
Point p = f(x); ——X哪来的？应该改成Point p = f(pt.x);
if(p.x > cache.x){——应该是if(p.y> cache.y)，比较的是不满意度
cache.x = p.x;}———改成
cache=p，不然不满意度无法更新
还有这样得到的结果是不满意度最大值，应该用<号
不满意度的算法好像也有问题
pt.y = (33-x)*(1+33-x)*3/2+(x-1)*(x-1+1)/2
LZ有几处错误
while((pt.x<33)){
pt.x++;
Point p = f(x); ——X哪来的？应该改成Point p = f(pt.x);
if(p.x > cache.x){——应该是if(p.y> cache.y)，比较的是不满意度
cache.x = p.x;}———改成
cache=p，不然不满意度无法更新
还有这样得到的结果是不满意度最大值，应该用<号
不满意度的算法好像也有问题
pt.y = (33-x)*(1+33-x)*3/2+(x-1)*(x-1+1)/2
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
终于有人看出来了
估计怪叔叔没看
但是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
估计怪叔叔没看
但是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字以内，仅用于支线交流，主线讨论请采用回复功能。
n=9999
for i=2 to 33
for j=2 to 33
if i>j then m=m+(i-j) else m=m+3*(j-i)
next
if m<n then n=m:k=i
m=0
next
msgbox n
msgbox k
我相当奇怪为啥我算出25........楼上几位的数学方法应该是27吧...
for i=2 to 33
for j=2 to 33
if i>j then m=m+(i-j) else m=m+3*(j-i)
next
if m<n then n=m:k=i
m=0
next
msgbox n
msgbox k
我相当奇怪为啥我算出25........楼上几位的数学方法应该是27吧...
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
我怎么好像记得答案是7？！
可能搞错了，那次数学课我在睡觉
可能搞错了，那次数学课我在睡觉
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
转自我的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是此时电梯停的楼层。
正确解法
思路：首先定义一个函数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字以内，仅用于支线交流，主线讨论请采用回复功能。
当电梯停在X层的时候,不满意度总和Y为Y=(1+....+(X-2))*1分 + (1+....+(33-x))*3分 【连加】
=(1+(X-2))*(x-2)/2*1分 + (1+(33-x))*(33-x)/2*3分 【连加使用高斯算法】
以上就可以直接交计算机干活
=(X-1)(X-2)(1/2)+(34-X)*(33-X)(3/2)
化简各位自便
=(1+(X-2))*(x-2)/2*1分 + (1+(33-x))*(33-x)/2*3分 【连加使用高斯算法】
以上就可以直接交计算机干活
=(X-1)(X-2)(1/2)+(34-X)*(33-X)(3/2)
化简各位自便
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
很明显是25
Noname怎么得到27的？
算了，此贴的是是非非，等我下个月回杭州再说
Noname怎么得到27的？
算了，此贴的是是非非，等我下个月回杭州再说
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
恩,,,,,我也在奇怪为什么是27.网上找的那年考试标准答案.....
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
25楼
附上一段比较低效的代码
// 电梯问题.cpp : 定义控制台应用程序的入口点。
//
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> vec(32);
for(int i=2;i<=33;i++)
{
int cache=0;
int upcache=0;
int downcache=0;
for(int a=1;a<=33-i;a++)
{
upcache+=3*a;
}
for(int a=0;a<=i-2;a++)
{
downcache+=a;
}
cache=upcache+downcache;
vec[i-2]=cache;
}
for(int i=0;i<33;i++)
{
cout<<i+1<<" "<<vec[i]<<endl;
}
}
附上一段比较低效的代码
// 电梯问题.cpp : 定义控制台应用程序的入口点。
//
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> vec(32);
for(int i=2;i<=33;i++)
{
int cache=0;
int upcache=0;
int downcache=0;
for(int a=1;a<=33-i;a++)
{
upcache+=3*a;
}
for(int a=0;a<=i-2;a++)
{
downcache+=a;
}
cache=upcache+downcache;
vec[i-2]=cache;
}
for(int i=0;i<33;i++)
{
cout<<i+1<<" "<<vec[i]<<endl;
}
}
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
回 17楼(bastogneyu) 的帖子
17楼的代码，看着才舒服一点。LZ的看着太累，不像专门玩这个的。
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
曾经我参加全国比赛，要求是这样的，求100 e之内的所有水仙花多数。 2个小时编程，程序需要在3分钟之内计算出来。 我用了好像是100秒左右。 可以使用多线程。
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。
回 20楼(cs_net) 的帖子
这个100 e指的是多少？
引用
加载评论中，请稍候...
200字以内，仅用于支线交流，主线讨论请采用回复功能。