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;}新闻热点
疑难解答
