题目链接:https://codeforces.com/contest/1856/problem/D
大致题意:
这是一道交互题,有1~n的排列p,对于每次询问,你可以花费(R-L)2的代价去得到区间【L,R】之内的逆序对的个数,
你需要在5n2的代价内得到n的位置。
初步思路:
首先我们来思路,在什么时候,我们可以确定那个位置是n。
假设n的位置是p,那么我们可以知道
1:区间[l,p-1]和区间[l,p]的逆序对的个数是一样。因为p之前没有比n大的数。
2:区间[l,p+1],[l,p+2],,,,[l,n]他们的逆序对至少比前面多1。因为p的位置是n,所以每次至少会产生一个逆序对。
所以我们可以知道一个区间【L,R】的最大值定理,对于【L,R】,我们询问【L,L+1】,【L,L+2】,,,【L,R】,最后一个不增加的位置就是最大值所在处;
所以我们可以有一个暴力的想法,那就是枚举【1,2】,【1,3】,,,,【1,n】,最后不增加的位置就是n的位置。
但是,显然,这是过不了这道题的,他的代价为,1^2+2^2+....+(n-1)^2,接近n^3。
我们考虑一下怎么优化,想到求解逆序对的时候我们用到了分治,所以我们思考分治:
把区间 [l,r]分成 [l,mid]和 [mid+1,r]两个区间,分别求出两个区间的最大值位置pl,pr,然后根据最大值定理,在这两个待选位置中求出整个 [l,r]的最大值位置。
具体方法就是层层递归分治,合并时判断 pr是否是区间[l,pr] 的最大值位置,如果是,由于分治说明了pr是区间[mid+1,r]最大值位置,则整个[l,r]的最大值位置就是 pr,否则,最大值位置就是 pl。
代价复杂度为:4n2,所以是可以通过的。
代码:
#include<bits/stdc++.h> int ask(int L, int R) { if (L == R)return 0; std::cout << "? " << L << " " << R << std::endl; std::cin >> L; return L; } int GO(int L, int R) { if (R == L)return L; int mid = (R + L) / 2; int ansl = GO(L, mid), ansr = GO(mid + 1, R); int pre = ask(ansl, ansr - 1), suf = ask(ansl, ansr); return pre == suf ? ansr : ansl; } signed main() { int T; std::cin >> T; while (T--) { int n; std::cin >> n; int ans = GO(1, n); std::cout << "! " << ans << std::endl; } return 0; }
可以看出,码量很短,是一道很妙的思维题呢!
- Constructor Codeforces Institute supported Roundconstructor codeforces institute supported 题解constructor codeforces institute educational codeforces round rated codeforces round 911 div codeforces round 864 div codeforces round 887 div codeforces round 913 div codeforces round 863 div codeforces round 915 div codeforces round 912 div