网易笔试4.11 第三题 错排
设序列为
当n为偶数时,很显然,相邻的两两交换,即与交换,与交换,以此类推生成错排。这样代价是最小的,因为错排与原排序中每个元素的距离都为1,代价为。
当n为奇数时,我们分情况。
设奇数位最小的为,x为对应的下标;偶数位最小的为,y为对应下标。
首先需要明确的一点是,n为奇数时,我们无法再通过类似n为偶数的情况,把相邻数对两两交换,因为必然会有一个是剩下的。剩下的这个,无论如何,在错排中与原排列的距离都会大于1。
若,最小的V在奇数。那么以下标x为分界条件,将错排分成三部分,后半部分为n-x个,且n-x为偶数,可以直接采用相邻交换的方式,这部分的距离都为1。而取x-2,x-1,x三个位置,作为中间部分,将其分别左移,则序列由原来的变为。除了的距离为2,其余都为1。对剩下的1~x-3同理,这部分为偶数个,距离都为1。反过来同理。
这种情况下,那个被剩下的距离不为1的元素,有着最小的V值,同时距离仅仅为2。很显然答案为。
若,最小的V在偶数位。此时我们再以下标y为分界条件,对错排进行划分。
若我们同样分成3部分,若让中间部分为奇数个。则此时,若不在中间部分的边缘,即是类似,那么无论是左移还是右移生成的错排序列,本身的距离都会为1,而有一个奇数位的边缘数字距离变为2。此时若该边缘数字为,则花销为。若不是则只会更大。
若是在边缘,类似,则此时前后部分必定为奇数个,必然会有某个的距离大于1,则总花销肯定大于。
若让中间部分为偶数个,则前后部分必然为奇数个。那么对其中任一部分,必然会有某个的距离大于1,则总花销肯定大于。
那么对最小的V在偶数的情况,可以分成两部分吗?同样的,若在边缘,比如在前半部分的末尾,如,则后半部分为奇数个,会存在某个的距离大于1,让总花销大于等于。若不在边缘,前半部分如。此时后半部分为偶数个,距离都为1。但对于前半部分,若采取左右移动的方式,总是边缘数字的距离为2,那么花销也是大于等于。至于其它的生成错排的方式,距离只会更大。
所以对于的情况,即最小的V在偶数位,开销也是必然大于等于,而采用跟时类似的划分就可以得到该下界了。
综上,
n为偶数,答案为。
n为奇数,答案为,其中为奇数位上最小的V值。
不保证证明正确,欢迎讨论。
其它两题就不放题解了。
#include <iostream> #include <vector> using namespace std; const int MAXN = 20 + 5; int main() { // freopen("in.txt", "r", stdin); int T; int n, x; cin >> T; while (T--) { int min_odd; long long sum = 0; cin >> n; for (int i = 1; i <= n; ++i) cin >> x; cin >> sum; min_odd = sum; for (int i = 2; i <= n; ++i) { cin >> x; sum += x; if (i & 1 != 0) min_odd = min(min_odd, x); } if (n & 1) cout << sum + min_odd << endl; else cout << sum << endl; } // fclose(stdin); return 0; }#网易##网易互娱##笔试题目#