题目地址
Problem B Bandits
ASC是质量很高的一套题目，在codeforces的gym上开放了第1~30套。
其中多为智商题。这也就意味着，如果一题不会做，你可能想很久，查阅了很多资料，还是不会做。前几套的题解可以在shi哥的博客上找到。后面的好像就没什么题解了。当然codeforces上的红色账号可以看到标程。可是既然是智商题，本来不会做的，看了标程也往往是不明白的……
随着我们team备战ACMICPC World Finals 2014，ASC 16-30都被我们训练过了，网络上又缺乏题解，于是考虑陆陆续续写一些我们team在训练时候没有想出来的题的题解。因为学校课程/实习面试/训练/英语课等原因，我自己时间也不是特别多，于是不可能像shi哥那样一套一套地完整写了。但是我写的题对于没有达到Topcoder Codeforces双红的算法竞赛选手大概还是很有意义的。
这个海盗分金是个经典问题，但是其实不容易想对。而且条件变一下策略也要跟着变化。这题题意是这样的：
有n个海盗和m块钱(1 ≤ n, m ≤ 2000)，他们要分这些钱。
分钱流程如下：先给每个强盗依次记上编号1~n。然后1号强盗提出一个钱的分配方案(也就是指定每个人获得多少钱)。剩下的人(包括1号强盗本身)对这个方案进行投票，如果支持提案的人数严格大于半数人，那么这个方案被通过，大家按数目分钱；而如果不通过，则大家把1号强盗杀掉。剩下的强盗编号都减一，人数减一，再次分钱。
假设强盗们都绝顶聪明，并且他们都认为彼此绝顶聪明。
一个强盗会反对投票，当且仅当他知道当前这个人被投死了以后，他一定会存活下来，并且获得至少和当前提案相当的金币。
现在，请你回答第一个强盗最多能提案分配给自己多少钱而不被杀。如果无论如何都会被杀，输出-1。
很容易想到倒着推，每个强盗用一个数值表示他在最坏情况下能获得的钱。可能死则用-1表示。然后每次在前面加入一个强盗，他就可以收买那些最容易收买的人。把后面的强盗的数值从小到大排序，给这些人的数值加一块钱，就能得到他的支持，用这种方式收集够票数以后，剩下的钱就是自己的了，于是把被他收拢的强盗的数值都加1，没被他收拢的强盗数值都设为0；而如果钱不够……那这个强盗就死定了，直接填入一个-1，别的强盗数值不变。代码如下：
#include
#include
#include
using namespace std;
int main(){
int m,n;
scanf("%d%d",&m,&n);
vector u;
u.push_back(n);
for(int i=2;i< =m;i++){
int c=i/2,sum=0;
vector v=u;
sort(v.begin(),v.end());
for(int j=0;jn){
u.insert(u.begin(),-1);
}else{
v.swap(u);
u.insert(u.begin(),n-sum);
}
}
printf("%d\n",u[0]);
}
然后你就会得到Wrong Answer on 36……问题出在哪里呢？
下面给出AC的代码可以先思考一下为什么。
#include
#include
#include
using namespace std;
int main(){
int m,n;
scanf("%d%d",&m,&n);
vector u;
u.push_back(n);
for(int i=2;i< =m;i++){
int c=i/2,sum=0;
vector v=u;
sort(v.begin(),v.end());
for(int j=0;j 0 && c < i - 1 && v[ c - 1 ] == v[ c ]) c--;
for(int j=0;jn){
u.insert(u.begin(),-1);
}else{
v.swap(u);
u.insert(u.begin(),n-sum);
}
}
printf("%d\n",u[0]);
}
可以看到，后面的代码和前面的差别在于对数值相等的强盗的变化进行了一些处理。
但是为什么是这样？我们甚至可以发现海盗算当前分配方案的时候sum值的计算和v值的修改是不对应的。可以先想一想而不急着看下文。
其实关键是：当前的这个海盗的选择具有任意性。
首先解决第一个问题，为何sum值和之前的计算一样？答案是当前强盗作出的决策必须能够收买超过半数人。
再来第二个问题，为何v值的变化要把和vc等值的被收买的强盗的v值也设为0？答案是这些强盗不知道当前强盗会不会选到自己，所以他们的最坏情况下得到的金币是0。
至此，该题得到了解决。