codeforces #336 div 2 A. Saitama Destroys Hotel

http://codeforces.com/contest/608/problem/A 题意：一个电梯，从s到0层，单项，给出n个人，每个人在某时间出现在某层，问要花多长时间把所有人运到0。初始电梯在s，每下一层话费时间1，上来人不花时间。思路：由于电梯只能是单项，那么到达某一层的时候，一定要等到把这层中最晚来的那个接走。所以排序的时候按照楼层高到低为第一关键字，等待时间长到短为第二关键字。对于同一楼层出现的，只考虑第一个即可，也就是最后出现的。需要注意的是最后接完最后一个人以后把电梯运行道0层。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2015年12月24日 星期四 00时32分24秒
 4File Name :code/cf/#336/A.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34int n;
35int s;
36struct node
37{
38    int f,t;
39
40    bool operator <(node b)const
41    {
42	if (f>b.f) return true;
43	if (f==b.f&&t>b.t) return true;
44	return false;
45    }
46}q[N];
47int main()
48{
49	#ifndef  ONLINE_JUDGE
50	freopen("code/in.txt","r",stdin);
51  #endif
52	cin>>n>>s;
53	for ( int i =  1 ; i<= n ;i++) cin>>q[i].f>>q[i].t;
54
55	sort(q+1,q+n+1);
56	int cur = s;
57	int t = 0 ;
58	q[0].f = -1;
59//	for ( int i = 1 ; i <= n ; i++) cout<<q[i].f<<" "<<q[i].t<<endl;
60	for ( int i = 1 ; i <= n ; i++)
61	{
62	    if (q[i].f==q[i-1].f) continue;
63	    t+=cur-q[i].f;
64	   // cout<<"t:"<<t<<" ";
65	    cur = q[i].f;
66	    if (t<q[i].t)
67	    {
68		t = q[i].t;
69	    }
70	  //  cout<<"t2:"<<t<<endl;
71	}
72	t+=q[n].f;
73	cout<<t<<endl;
74
75  #ifndef ONLINE_JUDGE
76  fclose(stdin);
77  #endif
78    return 0;
79}

相关文章