基本情况
A题当时做完提交一直编译错误后面发现是语言选择错误,浪费了五六分钟,然后去做B没想到去看C看了样例感觉可以做,结果干了好久都没出来,倒回去看B还是没做出来,感觉全程很紧张不知道为什么,脚一直在抖。
A. Brick Wall
没啥好说的,就是全部放竖直的,实在不能放了再放横的而且把横的宽度拉到最大就ok了
B. Minimize Inversions
当时卡在了不知道怎么同时处理A和B因为动了A的索引B也会改变。有一瞬间想到了把A数组按从小到大排,但觉得可能这个时候不是最小值;
其实把一个从小到大排就是最小值,一开始被样例骗了以为不能其实就按从小到大排最小的反转数是一摸一样的。那这个是为什么呢?
1.一开始就按从小到大排那么A的就全部是正序对,那么我们假设正变为逆-1,逆变为正+1,这样如果我们交换后只有更差或保持原样绝对不可能更好。
2.那么又会问,我上面说的是针对i和j相邻的,如果不相邻这样子影响的可不是只有1个会不会更好呢,其实是不会的因为假设这个i和j相差为x那么我们动A就会添加x个逆序对,那对于B来说呢,最好的情况就是添加x个正序对,这样一来最好的情况就是保持原样。
反思一下当时为什么想到了把A全部变为从小到大排而觉得不可以呢,第一点:看样例后觉得不可以其实应该继续思考就把我的答案代过去看逆序对数是否一样。第二点:想到了从小到大排发现了问题后就觉得是错误但是可能这个问题是不存在的需要证明出来这个问题