[已解决]最优选址类问题

linkz

在一个编号为0到1000的坐标轴上，假设有100个住户，每个住户的地址按0到1000随机编号。现在市长需要修一个公园，目的是让该公园到每一个市民家里的距离之和为最小值。因此，市长需要从每个市民那里收集信息，但是每个市民都极度自私，希望公园到自己家的距离最短。市长目前有三个备选方案：1.自己随机选择地址，不考虑任何信息。 2.将市民报告的地址按升序排列，选择排序后最左边的的地址。 3.统计好所有100个住户的地址后，求平均值 这三个备选方案的优缺点是什么，有没有一个新方法去得到更好的效果
限制条件：1.每个住户只能上报一次地址；2.每个市民都希望公园距离自己家的距离最小，因此可能会上报一个虚假的地址； 3.每个市民不知道彼此上报的地址，也就是信息不互通，不存在共谋行为。（修改下第三个条件，假如信息完全公开，每个居民都知道其他所有居民的地址）
新增两个条件，4. 居民的地址可以和公园的地址相同，也就是居民在1，公园也可以在1  5. 可以有几个居民的地址是一样的（有居民可能是一起住的公寓）
我这边想的是用random函数建立随机数，但是最开始时，每个住户本身又有一个精确的地址。现在就很头大，不知道该怎么用python去实现。有大佬在吗～可以一起讨论一下下，有代码更好哦！小弟在此谢过！！

最佳答案

月排行榜 / 总排行榜

java2python

2020-6-17 07:05:00

市长目前有三个备选方案：
1.自己随机选择地址，不考虑任何信息。
2.将市民报告的地址按升序排列，选择排序后最左边的的地址。
3.统计好所有100个住户的地址后，求平均值

【效果】
*****************************************
1.效果看运气
2.效果不佳，因为离最左边用户最近，那么公园位置往右移动一点，就是离这家虽然会远一点，但离其他99家都会近一点
3.相对1,2，效果最好（实际考虑到住户会谎报地址，也不是很完美）
*****************************************

限制条件：
1.每个住户只能上报一次地址；
2.每个市民都希望公园距离自己家的距离最小，因此可能会上报一个虚假的地址；
3.每个市民不知道彼此上报的地址

假设：
市民都是知道别的市民的地址
假设市民认为别的市民都是老实的

对市民来说
市长的方案1，他们的任何努力都是无效的
市长的方案2，取最左边的地址，也就是最小的地址，那么他们的努力也是无效的
市长的方案3，求公园离住户的平均值中最小的地点，这个他们才是他们的努力有效果的方案

市民知道后方案3后会采取的策略：
比如：假如100个住户的地址均匀分布在1-1000位置上，按照方案三，公园位置应该在500这个点上，
那么住址700位置住户，知道方案3，为了离自己近，他会报1000，如此公园位置会从500，向1000方向偏移一点。
同理，住址300的住户，会报0，这个不像住址700的住户那么的肯定，因为万一是采用方案2，这一上报，会使自己离公园更远。
而700的住户，他上报1000是不存在这种可能性的。

所以对单个住户来说，对于三个方案，他必须做到，让自己上报的住址，最后结果离自己最近：
*方案1：三分之一可能性，努力无效，这条在作为住户来说，他应该不考虑这种情况，他只考虑2,3对自己是好处还是坏处就行了
*方案2：三分之一可能性，住户应该如实上报自己地址
*方案3：三分之一可能性，住户应该上报平均后使公园往自己住址偏移的方案
--------------------------------------------------------
经过这个考虑过程，住址300的住户，会选择上报最左边住户的住址，因为万一是方案2，那么和本来一样，他没有损失，万一方案三，他得益

说了一大堆，如何程序化：
*随机生成100个住户住址
对于每个住户：
他上报1----------1000中一个：
        三分之一可能性：方案2，他最终离公园是多少
        三分之一可能性：方案3，他最终离公园是多少
两个之和后，取小的值。

方案2公园地址=最左住户
对用户N，他的方案测试：
最小距离和=10000
for 上报地址 = 0 -- 1000{
        方案3公园地址=100住户地址平均（其他住户就是原来地址，他的地址用的是上报地址）
        距离和=绝对值（他的实际住址-方案3公园地址)+绝对值(他的实际住址-方案2公园地址)
        if 距离和<最小距离和 {
                最小距离和 = 距离和
                最小距离住址 = 上报地址
        }
}
print(最小距离住址,最小距离和)

这是对于单个用户的，对于所有100个，就在外面再加一层循环。

跳转到最佳答案楼层

java2python

市长目前有三个备选方案：
1.自己随机选择地址，不考虑任何信息。
2.将市民报告的地址按升序排列，选择排序后最左边的的地址。
3.统计好所有100个住户的地址后，求平均值

【效果】
*****************************************
1.效果看运气
2.效果不佳，因为离最左边用户最近，那么公园位置往右移动一点，就是离这家虽然会远一点，但离其他99家都会近一点
3.相对1,2，效果最好（实际考虑到住户会谎报地址，也不是很完美）
*****************************************

限制条件：
1.每个住户只能上报一次地址；
2.每个市民都希望公园距离自己家的距离最小，因此可能会上报一个虚假的地址；
3.每个市民不知道彼此上报的地址

假设：
市民都是知道别的市民的地址
假设市民认为别的市民都是老实的

对市民来说
市长的方案1，他们的任何努力都是无效的
市长的方案2，取最左边的地址，也就是最小的地址，那么他们的努力也是无效的
市长的方案3，求公园离住户的平均值中最小的地点，这个他们才是他们的努力有效果的方案

市民知道后方案3后会采取的策略：
比如：假如100个住户的地址均匀分布在1-1000位置上，按照方案三，公园位置应该在500这个点上，
那么住址700位置住户，知道方案3，为了离自己近，他会报1000，如此公园位置会从500，向1000方向偏移一点。
同理，住址300的住户，会报0，这个不像住址700的住户那么的肯定，因为万一是采用方案2，这一上报，会使自己离公园更远。
而700的住户，他上报1000是不存在这种可能性的。

所以对单个住户来说，对于三个方案，他必须做到，让自己上报的住址，最后结果离自己最近：
*方案1：三分之一可能性，努力无效，这条在作为住户来说，他应该不考虑这种情况，他只考虑2,3对自己是好处还是坏处就行了
*方案2：三分之一可能性，住户应该如实上报自己地址
*方案3：三分之一可能性，住户应该上报平均后使公园往自己住址偏移的方案
--------------------------------------------------------
经过这个考虑过程，住址300的住户，会选择上报最左边住户的住址，因为万一是方案2，那么和本来一样，他没有损失，万一方案三，他得益

说了一大堆，如何程序化：
*随机生成100个住户住址
对于每个住户：
他上报1----------1000中一个：
        三分之一可能性：方案2，他最终离公园是多少
        三分之一可能性：方案3，他最终离公园是多少
两个之和后，取小的值。

方案2公园地址=最左住户
对用户N，他的方案测试：
最小距离和=10000
for 上报地址 = 0 -- 1000{
        方案3公园地址=100住户地址平均（其他住户就是原来地址，他的地址用的是上报地址）
        距离和=绝对值（他的实际住址-方案3公园地址)+绝对值(他的实际住址-方案2公园地址)
        if 距离和<最小距离和 {
                最小距离和 = 距离和
                最小距离住址 = 上报地址
        }
}
print(最小距离住址,最小距离和)

这是对于单个用户的，对于所有100个，就在外面再加一层循环。

jerryxjr1220

如果市民之间的信息是不共享的，那么要满足“希望公园到自己家的距离最短”，当然是直接上报公园就是自己家的位置，那么其实所有上报的点就是100个住户家的位置。然后不就是“最小二乘法”的问题了么？

linkz

jerryxjr1220 发表于 2020-6-17 07:49
如果市民之间的信息是不共享的，那么要满足“希望公园到自己家的距离最短”，当然是直接上报公园就是自己家 ...

对哦。那假如信息共享应该怎么算

linkz

java2python 发表于 2020-6-17 09:56
市长目前有三个备选方案：
1.自己随机选择地址，不考虑任何信息。
2.将市民报告的地址按升序排列，选择 ...

那请问有没有一个比三更好的方法呢 0-0

java2python

linkz 发表于 2020-6-18 05:30
那请问有没有一个比三更好的方法呢 0-0

即便是假定了每个住民，都会认为别的住民是老实的，他的实际地址和选址，你需要模拟一千次
而对于所有住民，你需要模拟100*1000次。
方案三比1,2好的基础，是每个住民都会如实上报，而实际根本不是这个情况，所以需要过滤不良信息。就是通过他的上报数据，还原他真是数据。比如700的上报1000，那么真实住址大概率是多少？或者说这个实际推不出。但30个人上报1000，那么他们真实住址的平均位于哪里，这个可能是能够比较确切知道的。
这个需要以前面100*1000次的模拟结果为基础。

java2python

用python模拟一下，结果如下：

平均住址： 520
真实地址=9,  虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=24,  虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=28,  虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=30,  虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=31,  虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=44,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=45,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=61,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=63,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=84,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=111,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=115,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=118,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=118,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=123,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=125,  虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=165,  虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=167,  虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=203,  虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=213,  虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=215,  虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=221,  虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=224,  虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=230,  虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=239,  虚报地址=8 ,方案二，方案三最短路径和=509
真实地址=256,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=286,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=289,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=289,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=311,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=313,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=328,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=332,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=335,  虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=349,  虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=357,  虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=390,  虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=397,  虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=408,  虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=411,  虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=421,  虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=429,  虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=442,  虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=454,  虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=464,  虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=492,  虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=508,  虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=510,  虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=531,  虚报地址=901 ,方案二，方案三最短路径和=529
真实地址=537,  虚报地址=907 ,方案二，方案三最短路径和=541
真实地址=554,  虚报地址=924 ,方案二，方案三最短路径和=575
真实地址=556,  虚报地址=926 ,方案二，方案三最短路径和=579
真实地址=595,  虚报地址=965 ,方案二，方案三最短路径和=657
真实地址=598,  虚报地址=968 ,方案二，方案三最短路径和=663
真实地址=598,  虚报地址=968 ,方案二，方案三最短路径和=663
真实地址=607,  虚报地址=977 ,方案二，方案三最短路径和=681
真实地址=614,  虚报地址=984 ,方案二，方案三最短路径和=695
真实地址=622,  虚报地址=992 ,方案二，方案三最短路径和=711
真实地址=625,  虚报地址=995 ,方案二，方案三最短路径和=717
真实地址=632,  虚报地址=902 ,方案二，方案三最短路径和=732
真实地址=642,  虚报地址=912 ,方案二，方案三最短路径和=752
真实地址=647,  虚报地址=917 ,方案二，方案三最短路径和=762
真实地址=659,  虚报地址=929 ,方案二，方案三最短路径和=786
真实地址=685,  虚报地址=955 ,方案二，方案三最短路径和=838
真实地址=693,  虚报地址=963 ,方案二，方案三最短路径和=854
真实地址=695,  虚报地址=965 ,方案二，方案三最短路径和=858
真实地址=695,  虚报地址=965 ,方案二，方案三最短路径和=858
真实地址=704,  虚报地址=974 ,方案二，方案三最短路径和=876
真实地址=706,  虚报地址=976 ,方案二，方案三最短路径和=880
真实地址=722,  虚报地址=992 ,方案二，方案三最短路径和=912
真实地址=736,  虚报地址=906 ,方案二，方案三最短路径和=941
真实地址=778,  虚报地址=948 ,方案二，方案三最短路径和=1025
真实地址=783,  虚报地址=953 ,方案二，方案三最短路径和=1035
真实地址=789,  虚报地址=959 ,方案二，方案三最短路径和=1047
真实地址=789,  虚报地址=959 ,方案二，方案三最短路径和=1047
真实地址=798,  虚报地址=968 ,方案二，方案三最短路径和=1065
真实地址=801,  虚报地址=971 ,方案二，方案三最短路径和=1071
真实地址=806,  虚报地址=976 ,方案二，方案三最短路径和=1081
真实地址=810,  虚报地址=980 ,方案二，方案三最短路径和=1089
真实地址=827,  虚报地址=997 ,方案二，方案三最短路径和=1123
真实地址=843,  虚报地址=913 ,方案二，方案三最短路径和=1156
真实地址=847,  虚报地址=917 ,方案二，方案三最短路径和=1164
真实地址=848,  虚报地址=918 ,方案二，方案三最短路径和=1166
真实地址=851,  虚报地址=921 ,方案二，方案三最短路径和=1172
真实地址=855,  虚报地址=925 ,方案二，方案三最短路径和=1180
真实地址=859,  虚报地址=929 ,方案二，方案三最短路径和=1188
真实地址=877,  虚报地址=947 ,方案二，方案三最短路径和=1224
真实地址=892,  虚报地址=962 ,方案二，方案三最短路径和=1254
真实地址=895,  虚报地址=965 ,方案二，方案三最短路径和=1260
真实地址=926,  虚报地址=996 ,方案二，方案三最短路径和=1322
真实地址=942,  虚报地址=912 ,方案二，方案三最短路径和=1355
真实地址=954,  虚报地址=924 ,方案二，方案三最短路径和=1379
真实地址=958,  虚报地址=928 ,方案二，方案三最短路径和=1387
真实地址=962,  虚报地址=932 ,方案二，方案三最短路径和=1395
真实地址=971,  虚报地址=941 ,方案二，方案三最短路径和=1413
真实地址=981,  虚报地址=951 ,方案二，方案三最短路径和=1433
真实地址=981,  虚报地址=951 ,方案二，方案三最短路径和=1433
真实地址=984,  虚报地址=954 ,方案二，方案三最短路径和=1439
真实地址=996,  虚报地址=966 ,方案二，方案三最短路径和=1463
真实地址=997,  虚报地址=967 ,方案二，方案三最短路径和=1465

import random
#import math

class Address:
    
    def __init__(self,true_addr):
        self.true_addr = true_addr
        self.min_distance = 10000
        self.min_addr = 0

    def print_msg(self):
        return "真实地址=%d,  虚报地址=%d ,方案二，方案三最短路径和=%d" % (self.true_addr,self.min_addr,self.min_distance)
    
true_addr = []
for i in range(100):
    true_addr.append(random.randint(0,1000))
true_addr.sort()

min_addr = min(true_addr)
sum_addr = sum(true_addr)
all_addr = []
for t in true_addr:
    addr = Address(t)
    for a in range(1001):
        plan2_addr = min(a,min_addr)
        plan3_addr = (sum_addr+(a - t))//100
        distance = abs(t-plan2_addr)+abs(t-plan3_addr)
        if distance < addr.min_distance:
            addr.min_distance = distance
            addr.min_addr = a
    all_addr.append(addr)

print("平均住址：",sum_addr//100)
for a in all_addr:
    print(a.print_msg())

java2python

经过许多次测试：
真实地址=11,  虚报地址=11 ,方案二，方案三最短路径和=461
真实地址=33,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=50,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=57,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=59,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=71,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=82,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=83,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=88,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=90,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=90,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=92,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=94,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=101,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=113,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=115,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=118,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=126,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=126,  虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=155,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=166,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=168,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=172,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=177,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=178,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=185,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=191,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=204,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=225,  虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=238,  虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=274,  虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=278,  虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=285,  虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=292,  虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=337,  虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=350,  虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=355,  虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=361,  虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=370,  虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=378,  虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=407,  虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=415,  虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=432,  虚报地址=10 ,方案二，方案三最短路径和=457
真实地址=436,  虚报地址=11 ,方案二，方案三最短路径和=456
真实地址=440,  虚报地址=11 ,方案二，方案三最短路径和=456
真实地址=450,  虚报地址=11 ,方案二，方案三最短路径和=456
真实地址=452,  虚报地址=11 ,方案二，方案三最短路径和=456
真实地址=470,  虚报地址=249 ,方案二，方案三最短路径和=459          <---虚报地址发生变动的那个住户，是离平均值最近的，只需要调查这个用户的真是地址就行了
真实地址=483,  虚报地址=962 ,方案二，方案三最短路径和=478
真实地址=501,  虚报地址=980 ,方案二，方案三最短路径和=514
真实地址=506,  虚报地址=985 ,方案二，方案三最短路径和=524
真实地址=506,  虚报地址=985 ,方案二，方案三最短路径和=524
真实地址=508,  虚报地址=987 ,方案二，方案三最短路径和=528
真实地址=513,  虚报地址=992 ,方案二，方案三最短路径和=538
真实地址=517,  虚报地址=996 ,方案二，方案三最短路径和=546
真实地址=523,  虚报地址=902 ,方案二，方案三最短路径和=559
真实地址=531,  虚报地址=910 ,方案二，方案三最短路径和=575
真实地址=536,  虚报地址=915 ,方案二，方案三最短路径和=585
真实地址=545,  虚报地址=924 ,方案二，方案三最短路径和=603
真实地址=554,  虚报地址=933 ,方案二，方案三最短路径和=621
真实地址=577,  虚报地址=956 ,方案二，方案三最短路径和=667
真实地址=591,  虚报地址=970 ,方案二，方案三最短路径和=695
真实地址=592,  虚报地址=971 ,方案二，方案三最短路径和=697
真实地址=595,  虚报地址=974 ,方案二，方案三最短路径和=703
真实地址=596,  虚报地址=975 ,方案二，方案三最短路径和=705
真实地址=605,  虚报地址=984 ,方案二，方案三最短路径和=723
真实地址=624,  虚报地址=903 ,方案二，方案三最短路径和=762
真实地址=636,  虚报地址=915 ,方案二，方案三最短路径和=786
真实地址=656,  虚报地址=935 ,方案二，方案三最短路径和=826
真实地址=667,  虚报地址=946 ,方案二，方案三最短路径和=848
真实地址=689,  虚报地址=968 ,方案二，方案三最短路径和=892
真实地址=695,  虚报地址=974 ,方案二，方案三最短路径和=904
真实地址=696,  虚报地址=975 ,方案二，方案三最短路径和=906
真实地址=714,  虚报地址=993 ,方案二，方案三最短路径和=942
真实地址=734,  虚报地址=913 ,方案二，方案三最短路径和=983
真实地址=735,  虚报地址=914 ,方案二，方案三最短路径和=985
真实地址=740,  虚报地址=919 ,方案二，方案三最短路径和=995
真实地址=768,  虚报地址=947 ,方案二，方案三最短路径和=1051
真实地址=774,  虚报地址=953 ,方案二，方案三最短路径和=1063
真实地址=775,  虚报地址=954 ,方案二，方案三最短路径和=1065
真实地址=784,  虚报地址=963 ,方案二，方案三最短路径和=1083
真实地址=801,  虚报地址=980 ,方案二，方案三最短路径和=1117
真实地址=802,  虚报地址=981 ,方案二，方案三最短路径和=1119
真实地址=817,  虚报地址=996 ,方案二，方案三最短路径和=1149
真实地址=822,  虚报地址=901 ,方案二，方案三最短路径和=1160
真实地址=822,  虚报地址=901 ,方案二，方案三最短路径和=1160
真实地址=823,  虚报地址=902 ,方案二，方案三最短路径和=1162
真实地址=824,  虚报地址=903 ,方案二，方案三最短路径和=1164
真实地址=828,  虚报地址=907 ,方案二，方案三最短路径和=1172
真实地址=830,  虚报地址=909 ,方案二，方案三最短路径和=1176
真实地址=834,  虚报地址=913 ,方案二，方案三最短路径和=1184
真实地址=842,  虚报地址=921 ,方案二，方案三最短路径和=1200
真实地址=848,  虚报地址=927 ,方案二，方案三最短路径和=1212
真实地址=852,  虚报地址=931 ,方案二，方案三最短路径和=1220
真实地址=870,  虚报地址=949 ,方案二，方案三最短路径和=1256
真实地址=879,  虚报地址=958 ,方案二，方案三最短路径和=1274
真实地址=932,  虚报地址=911 ,方案二，方案三最短路径和=1381
真实地址=943,  虚报地址=922 ,方案二，方案三最短路径和=1403
真实地址=964,  虚报地址=943 ,方案二，方案三最短路径和=1445
真实地址=982,  虚报地址=961 ,方案二，方案三最短路径和=1481
真实平均住址： 472
虚报平均住址： 499
小于平均住址的住户数： 48
小于虚报平均住址的住户数： 48

linkz

java2python 发表于 2020-6-18 11:07
经过许多次测试：
真实地址=11,  虚报地址=11 ,方案二，方案三最短路径和=461
真实地址=33,  虚报地址=11 ...

假如市长提前已经确定了方案2或者方案3，居民们也都知道市长确定的方案，是不是最后算绝对值那里就需要换式子了？大佬你的代码是不是相当于是一个将方案2和3结合在一起的新方案？

linkz

java2python 发表于 2020-6-18 09:57
用python模拟一下，结果如下：

真的太感谢，居然还费心写了这么多代码！！

java2python

linkz 发表于 2020-6-19 08:11
假如市长提前已经确定了方案2或者方案3，居民们也都知道市长确定的方案，是不是最后算绝对值那里就需要换 ...

不是大佬。
这个题目：市长有三个方案，这个是公开的，市民当然应该知道。
实际市民的努力只有在市长采用方案三的时候才能体现：比如最左住址是15，这位市民的住址是100，为了让平均住址往100方向移动（正常是500左右），他应该虚报住址0，但是考虑到市长可能采用方案二，这样，他虚报0，公园反而比原来往左移了15，离他更远了。
因为市民不知道市长会采用哪个方案，所以应该要把方案二，方案三的距离加起来。是这个意思。
对市民来说，他是这么考虑的，那么市长需要在市民上报数据的基础上，考虑到这个，对数据进行过滤。
但实际呢，要恢复到真实数据，是很困难的。
对题目，并不是说要完美解决这个题目，进行一定的思考，用某种方案去尝试解决，这过程有些时候不是一步到达。必须模拟看看，发现数据中有什么规律，然后在此基础上，再尝试处理。总之我的表达能力很有限，就是这么个意思。

linkz

java2python 发表于 2020-6-19 08:26
不是大佬。
这个题目：市长有三个方案，这个是公开的，市民当然应该知道。
实际市民的努力只有在市长采 ...

不不，我的意思是，单独讨论方案2和方案3，相当于市长只公布2、3中的一个，市民知道市长颁布这一个方案后进行上报。

java2python

linkz 发表于 2020-6-20 03:20
不不，我的意思是，单独讨论方案2和方案3，相当于市长只公布2、3中的一个，市民知道市长颁布这一个方案后 ...

如果只公布方案2，取最左住民的地址，那么市民就随意报了（当然不会报比最左的还小，那样更远，没好处），因为他们改变不了什么，当然最左的住民离公园最近，他一定是报真是地址的。
如果只公布方案3，那么左边的住户的一定会报0，这样能把公园往自己方向拉，右边一定会报1000，同样道理。
市长公布了1,2,3三个方案，实际住民认为这三个都有可能，在这种情况下，因为对于方案一，是随机的，他们改变不了什么，那么针对方案2，方案3，他们会尽力选择自己有利的数据上报。

linkz

java2python 发表于 2020-6-20 03:33
如果只公布方案2，取最左住民的地址，那么市民就随意报了（当然不会报比最左的还小，那样更远，没好处） ...

好叻，谢谢大佬，这么晚还在

pl_014

1.排除虚报情况，因为普通算法里考虑这种情况不现实。
2.想要求最短距离之和，首先你要知道距离之和怎么求。给个公式
假设p为公园位置，a[i]为第i个居民的位置
那么距离之和的求法是
for (; i < 100; i++)
{
    sum = sum+abs(p-a[i]);
}
3.要找最优解，因为地址只有1001个，所以可以直接暴力求解，把公园可能的1001个位置都算一遍，求最小值
4.优化：最优解的最小值不可能小到最小地址，最大值不可能高于最大地址，所以小于最小地址和大于最大地址的选项就不用算了
5.像求中位数、平均值等算法求得的都是近似的最优解，但并不是最优解，可以理解为贪心法。