Time Limit: 1 second Memory Limit: 128 MB
【問題描述】
小明要搬家了，大家都來幫忙。 小明現在住在第N樓，總共K個人要把X個大箱子搬上N樓。 最開始X個箱子都在1樓，但是經過一段混亂的搬運已經亂掉了。最后大家發現這樣混亂地搬運過程效率太低了，于是總結出了提高 效率的方法。 大家的速度都是每分鐘上（或下）一層樓。所有向上走的人手中都拿一個箱子，所有向下走的人都不拿箱子。到達第N層立刻放下箱 子向下走，到達第一層立刻拿起箱子向上走。當一個人向上走，另一個向下走而在樓道里相遇時，向上走的人將手中的箱子交 給另一個人，兩人同時反向。即原來拿箱子向上走的人不拿箱子向下走，原來不拿箱子向下走的人現拿著箱子向上走。 【數據范圍】 對于30%的數據有K≤100，M≤100； 對于60%的數據有K≤1000，M≤109； 對于100%的數據有K≤500000,M≤109
【輸入格式】
第一行N（N≤10^9）,K（K≤500000），M（M≤10^9）分別表示樓層數、人數、還放在一樓地上的箱子數。 接下來K行，每行兩個數Ai，Bi。 Ai表示第i人現在所在的層數，Bi為0或1，為0表示第i人正拿著箱子向上走，為1表示第i人不拿箱子向下走。 輸入滿足沒有任意兩人正在同一樓層，在第一層的人一定正拿著箱子向上走，在第N層的人一定正不拿箱子向下走。 【輸出格式】
僅包含一個整數，為搬完箱子的時間。
Sample Input
5 2 4 1 0 3 0
Sample Output
20
【題目鏈接】:http://noi.qz5z.com/viewtask.asp?id=t101
【題意】
【題解】 考慮一下兩個人相遇的情況; 必然是有一個人拿著一個箱子往上走;另外一個人空著手往下走; 之后他們交換了箱子,然后各自轉身; 其實這個過程就相當于一個人能夠穿過另外一個人往前走; 根本沒有想象的那么復雜; (拿箱子的人往上走,穿過那個空著手往下走的人;然后那個空著手往下走的人也空著手穿過那個往上走的人;都互相穿過了); 那么也就是說每個人的行動都是獨立的; 所以可以一個人一個人地考慮 這個時候我們就可以建立一個一維的坐標了; 考慮從下往上走的人由低到高從左往右放置; 考慮從上往下走的人,嚴格比往上走的人右,然后從高到低,也是從左往右地放; 然后看看m%k等于多少; 如果為0的話; 則每個人再拿m/k個箱子; 最后到達頂端的人所用的時間就是總時間; 則肯定是坐標軸上最左邊的那個人了; 如果m%k不等于0; 就說明箱子不夠每個人分一樣多; 那么從右往左數m%k個人的范圍內每個人都多拿一個箱子; 則取從右往左數第m%k個人; 它肯定是最后到的; 也即由他決定最后的時間;當然此時他要再拿的箱子數為m/k + 1; 然后模擬這個special的人它拿箱子的過程就好,求出最后的時間,也就是答案了. (程序中的坐標軸我轉了個方向,也就是和上面的題解的方向相反了,這樣好處理一點,當然坐標軸你要寫個排序才能搞出來) 【完整代碼】
#include<cstdio>#include <iostream>#include <algorithm>#include <cmath>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int K = 5e5+100;struct abc{ LL now; int p;};LL n,m;int k;abc ren[K];bool cmp(abc a,abc b){ if (a.p!=b.p) return a.p > b.p; else { int t = a.p; if (t==0) return a.now > b.now; else return a.now < b.now; }}int main(){ //freopen("F://rush.txt","r",stdin); rel(n),rei(k),rel(m); rep1(i,1,k) rel(ren[i].now),rei(ren[i].p); sort(ren+1,ren+1+k,cmp); LL t = m % k; if (t==0) t = k; abc sp = ren[t]; LL need = m/k; if (t!=k) need++; int p = sp.p; LL cost; if (p==0) cost = n-sp.now+n-1; else cost = sp.now-1; cost += 1LL*(2*(need-1)+1)*(n-1); cout << cost << endl; return 0;}新聞熱點
疑難解答
