信息学集训队作业ural

1、Ural1481 Winning chan解题浙江省杭州二中骞题目大意：给出 N 个质量互不相等，且不超过 1000 的砝码。和一个由“L”，“R”组成的长度为 N的序列 S，要求给出一种在天平上放置砝码的方案（砝码一旦放上，不再取下），使得放置下第 I 个砝码之后，天平往SI处偏（“L”表示左，“R”表示右）。方法：先对 N 个砝码从轻到重进行排序，得到 W。其中WI表示第 I 轻的砝码的质量。统计 S 中天平状态改变的次数 m，比如“LRLLR”改变了 4 次，分别是第一次（因为初始时天平是平衡状态），第二次，第三次，第五次。接下来构造放置方案。然后从左往右扫描 S：定义两个变量，分别是

2、a 和 b，初始时 an-m，b=n-m+1。如果天平状态改变，假设新状态偏向X（X = “L”或X = “R”），那么就在天平的 X侧放上重为Wb的砝码，b = b+1。如果天平状态没有改变，本来就偏向 X，那么要放置重量为 Wa的砝码。如果这个砝码放置在 X 的另一侧，天平仍然偏向 X，那么就将其放在 X 的另一侧，否则放在 X 侧。放完以后，a = a-1。证明：如果放下某个砝码后天平状态不改变，那么构造方案是对的，只要证明每次天平状态改变的时候放置的方法显然是对的。因此，要证明放的砝码足够让它改变。也就是，新放下的砝码，要比原来天平两边的重量差要大。命题：在任何时刻，假设天平两边的重量

3、差为a（a0），那么 a 一定小于等于现在天平中最重的一个砝码 wmax；且 a 大于等于现在天平中最轻的一个砝码 wmin，或者 a 加上最轻的砝码的重量 wmin 仍小于等于天平中最重的一个砝码 wmax。也就是 (a 0) and (a = wmin or a+wmin = wmax)用数学归纳法证明：初始：天平上只有一个砝码w，那么 wmax = wmin = a = w，命题成立。递推：某一时刻命题成立，现在在天平上新放上一个砝码 x，有两种情况： 1、 放上这个砝码后天平状态改变由放置的方法可知 x 大于现在天平上任何一个砝码，所以放置后新的状态下wmax = x, a = x-a

4、, wmin = wmin因为 a wmax 0因为 a 0，所以 a = x-a = wmin，那么 a+wmin = a+wmin = a+a = x否则 a+wmin = wmax-a = wmin = wmin（1）（2）（3）（4）由（1）、（2）、（3）、（4）得在第 1 种情况下，放置一个砝码后命题仍然成立。2、 放上这个砝码后天平状态没有改变由放置的方法可知 x 小于现在天平上任何一个砝码，所以放置后新的状态下wmax = wmax, wmin = x。现在又由两个小情况1） a a，也就是a = x+a 的时候，此时由放置的方法可知，wmin x = a，所以(a = wmi

5、n)一定为假，故(a+wmin = wmax)一定为真。所以有 a = a+x a+wmin 0，所以 a = a+x x = wmin a = x+a a 0（5）（6）（7）由（5）、（6）、（7）2） a a，也就是a = a-x在这种情况下命题仍然成立。的时候此时由放置的方法可知，x 0 a = a-x a wmax = wmaxa+wmin = a+x = a wmax = wmax由（8）、（9）、（10）得在此情况下命题仍然成立。（8）（9）（10）综上，命题成立。因为任何时刻重量差都小于等于当前天平上最重的一个砝码，且要改变状态时，总是放上一个比当前天平上任何砝码都重的一个砝码

6、，所以天平的状态一定会改变。所以造方法是对的。的构程序#include #include #include n;char s51;wei50;cmp(const void *a, const void *b)return *(*)a-*(*)b;main()freopen(a.in, r, stdin);freopen(a.out, w, stdout); scanf(%d, &n);for(i=0; in; i+)scanf(%d, &weii);qsort(wei, n, sizeof(), cmp);scanf(%s, s); k = n-1;for(i=0; in-1; i+)if (si != si+1)k-;j = k-1;wl = 0, wr = 0;for