[TIOJ]1172. 握手症候群

題目連結：http://tioj.infor.org/problems/1172

nth_element() 可以將第n個放在陣列第n個位置而他的左方是比他的，右方是比他大的。
而d陣列具有單調性，所以我們可以用二分的方法去做。
d[i]在左邊就用左邊的陣列去做，右邊亦然。
#include "lib1172.h"
#include <algorithm>
using namespace std;
int aa[1000005],b[105],r[105];
void find(int l,int r,int ll,int rr){
    if(l == r || rr == ll)return;
    nth_element(aa+l,aa+b[(ll+rr)/2],aa+r,[](int x,int y){return comp(x,y);});
    find(l,b[(ll+rr)/2],ll,(ll+rr)/2);
    find(b[(ll+rr)/2]+1,r,(ll+rr)/2+1,rr);
}
void query(int n,int d[],int l,int ans[]){
    for(int i = 0 ; i < n ; i++)aa[i] = i;
    for(int j = 0 ; j < l ; j++)b[j] = d[j];
    find(0,n,0,l);
    for(int i = 0; i < l; i ++)ans[i] = aa[d[i]];
}

留言

張貼留言

這個網誌中的熱門文章

[TIOJ]1617. [Interactive] 中位數

題目連結： http://tioj.infor.org/problems/1617 大家如果想一下肯定發現一個性質，Med3() 對於三個數字，會回傳中間值，而掃過整個序列，必能找出最大值與最小值的位置， 當然就可以透過這個方法，找n/2次，最後剩下的那個數字就是中位數，但這樣顯然會用太多次Med3()。 因為你已經找出這個序列的極值，那隨便找另外兩個數字和其中一個極值作Med3()會等同於比較那兩個數字的大小（因為極值不可能是中位數），因此可以用sort函式來排序，中間值就是中位數。 # include " lib1617.h " # include < algorithm > int a,b,n,k,v[ 1505 ]; int main (){ n = Get_Box(); if(n == 1) Report (1); a = 1;b = 2; for(int i = 3; i <= n ; i++){ int k = Med3(a,b,i); if(a == k)a = i; if(b == k)b = i; } for(int i = 1 ; i <= n ; i++)if(i != a and i != b)v[k++] = i; std::sort(v,v+n-2,[](int x,int y){ int tmp = Med3(a,x,y); return tmp == x ? 1 : 0; }); Report(v[(n-2)/2]); return 0; } 這樣只能拿40分。 不保證AC解法： 比中位數小的數字個數會等於比中位數大的數字個數，因此我們先找出這個序列的極值，然後隨機找一個數 t 並算出比 v[t] 小和大的個數，而整個序列的中位數在目前序列中會有 k 個數字比v[t]小，如果比v[t]小的數字個數剛好等於 k ，那就找到整個序列的中位數，如果> k 那就改成在比v[t]小的那個陣列內找答案，如果< k那就必須在比v[t]大的那個陣列找答案，且k要減l.size()+1。 顯然如果隨機數選的不...
繼續閱讀

[TIOJ]1994. 冰塊線

題目連結： http://tioj.infor.org/problems/1994 裸裸的遞迴下去，判斷朝向哪一邊即可～ 我的code挺暴力的>< # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int a[ 2050 ][ 2050 ]; void make (int x,int y,int l,int r,int sta){ if(r - l == 3){ if(sta == 1)a[x][y] = l,a[x+1][y] = l+1,a[x+1][y+1] = r-1,a[x][y+1] = r; if(sta == 2)a[x][y] = l,a[x+1][y] = r,a[x+1][y+1] = r-1,a[x][y+1] = l+1; if(sta == 3)a[x][y] = r-1,a[x+1][y] = r,a[x+1][y+1] = l,a[x][y+1] = l+1; if(sta == 4)a[x][y] = r-1,a[x+1][y] = l+1,a[x+1][y+1] = l,a[x][y+1] = r; return; } int t = (r-l+1)/4; int p = sqrt(r-l+1)/2; if(sta ...
繼續閱讀

[TIOJ]1337. 隕石

題目連結： http://tioj.ck.tp.edu.tw/problems/1337 因為答案具有單調性，所以可以對答案二分搜。 驗證答案的時候可以從左掃過去，如果這一點的隕石數量大於當前防護罩數量的話就需要把隕石打掉，打掉右界最大值的那一顆隕石會是最佳解（用priority_queue維護），最後檢查隕石數量有沒有大於上限即可。 因為數值範圍太大所以要離散化。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int n,k; vector< int > v; vector<Pair> l; int b[ 200005 ]; bool check (int x){ priority_queue<int, vector<int> , less<int> > pq; fill(b,b+200005,0); int p = 0,t = 0,m = k; for(int i = 0 ; i < v. size () ; i++){ while(p < n && l[p] .F == i)t++,b[l[p] .S ]++,pq. push (l[p] .S ),p++; if(b[i])t -= b[i]; in...
繼續閱讀