C++ STL中Map的按Key排序和按Value排序

map是用来存放键值对的数据结构,可以很方便快速的根据key查到相应的value。假如存储学生和其成绩(假定不存在重名,当然可以对重名加以区分),我们用map来进行存储就是个不错的选择。 我们这样定义,map,其中学生姓名用string类型,作为Key;该学生的成绩用int类型,作为value。这样一来,我们可以根据学生姓名快速的查找到他的成绩。

        但是,我们除了希望能够查询某个学生的成绩,或许还想看看整体的情况。我们想把所有同学和他相应的成绩都输出来,并且按照我们想要的顺序进行输出:比如按照学生姓名的顺序进行输出,或者按照学生成绩的高低进行输出。换句话说,我们希望能够对map进行按Key排序或按Value排序,然后按序输出其键值对的内容。

一、C++ STL中Map的按Key排序

       其实,为了实现快速查找,map内部本身就是按序存储的(比如红黑树)。在我们插入键值对时,就会按照key的大小顺序进行存储。这也是作为key的类型必须能够进行<运算比较的原因。现在我们用string类型作为key,因此,我们的存储就是按学生姓名的字典排序储存的。

【参考代码】

  1. #include
      
  2. #include  
  3. #include  
  4. using namespace std;  
  5.   
  6. typedef pairint> PAIR;  
  7.   
  8. ostream& operator<<(ostream& out, const PAIR& p) {  
  9.   return out << p.first << “t” << p.second;  
  10. }  
  11.   
  12. int main() {  
  13.   mapint> name_score_map;  
  14.   name_score_map[“LiMin”] = 90;   
  15.   name_score_map[“ZiLinMi”] = 79;   
  16.   name_score_map[“BoB”] = 92;   
  17.   name_score_map.insert(make_pair(“Bing”,99));  
  18.   name_score_map.insert(make_pair(“Albert”,86));  
  19.   for (mapint>::iterator iter = name_score_map.begin();  
  20.        iter != name_score_map.end();  
  21.        ++iter) {  
  22.     cout << *iter << endl;  
  23.   }  
  24.   return 0;  
  25.  }  

【运行结果】

 

大家都知道map是stl里面的一个模板类,现在我们来看下map的定义:

 

  1. template < class Key, class T, class Compare = less,  
  2.            class Allocator = allocatorconst Key,T> > > class map;  

它有四个参数,其中我们比较熟悉的有两个: Key 和 Value。第四个是 Allocator,用来定义存储分配模型的,此处我们不作介绍。

 

现在我们重点看下第三个参数: class Compare = less 

这也是一个class类型的,而且提供了默认值 less。 less是stl里面的一个函数对象,那么什么是函数对象呢?

所谓的函数对象:即调用操作符的类,其对象常称为函数对象(function object),它们是行为类似函数的对象。表现出一个函数的特征,就是通过“对象名+(参数列表)”的方式使用一个 类,其实质是对operator()操作符的重载。

现在我们来看一下less的实现:

 

  1. template <class T> struct less : binary_function bool> {  
  2.   bool operator() (const T& x, const T& y) const  
  3.     {return x
  4. };  


它是一个带模板的struct,里面仅仅对()运算符进行了重载,实现很简单,但用起来很方便,这就是函数对象的优点所在。stl中还为四则运算等常见运算定义了这样的函数对象,与less相对的还有greater:

 

 

  1. template <class T> struct greater : binary_function bool> {  
  2.   bool operator() (const T& x, const T& y) const  
  3.     {return x>y;}  
  4. };  


map这里指定less作为其默认比较函数(对象),所以我们通常如果不自己指定Compare,map中键值对就会按照Key的less顺序进行组织存储,因此我们就看到了上面代码输出结果是按照学生姓名的字典顺序输出的,即string的less序列。

 

我们可以在定义map的时候,指定它的第三个参数Compare,比如我们把默认的less指定为greater:

【参考代码】

  1. #include
      
  2. #include  
  3. #include  
  4. using namespace std;  
  5.   
  6. typedef pairint> PAIR;  
  7.   
  8. ostream& operator<<(ostream& out, const PAIR& p) {  
  9.   return out << p.first << “t” << p.second;  
  10. }  
  11.   
  12. int main() {  
  13.   mapint, greater > name_score_map;  
  14.   name_score_map[“LiMin”] = 90;   
  15.   name_score_map[“ZiLinMi”] = 79;   
  16.   name_score_map[“BoB”] = 92;   
  17.   name_score_map.insert(make_pair(“Bing”,99));  
  18.   name_score_map.insert(make_pair(“Albert”,86));  
  19.   for (mapint>::iterator iter = name_score_map.begin();  
  20.        iter != name_score_map.end();  
  21.        ++iter) {  
  22.     cout << *iter << endl;  
  23.   }  
  24.   return 0;  
  25. }  

【运行结果】

 

现在知道如何为map指定Compare类了,如果我们想自己写一个compare的类,让map按照我们想要的顺序来存储,比如,按照学生姓名的长短排序进行存储,那该怎么做呢?

 

其实很简单,只要我们自己写一个函数对象,实现想要的逻辑,定义map的时候把Compare指定为我们自己编写的这个就ok啦。

 

  1. struct CmpByKeyLength {  
  2.   bool operator()(const string& k1, const string& k2) {  
  3.     return k1.length() < k2.length();  
  4.   }  
  5. };  

 

是不是很简单!这里我们不用把它定义为模板,直接指定它的参数为string类型就可以了。

【参考代码】

  1. int main() {  
  2.   mapint, CmpByKeyLength> name_score_map;  
  3.   name_score_map[“LiMin”] = 90;   
  4.   name_score_map[“ZiLinMi”] = 79;   
  5.   name_score_map[“BoB”] = 92;   
  6.   name_score_map.insert(make_pair(“Bing”,99));  
  7.   name_score_map.insert(make_pair(“Albert”,86));  
  8.   for (mapint>::iterator iter = name_score_map.begin();  
  9.        iter != name_score_map.end();  
  10.        ++iter) {  
  11.     cout << *iter << endl;  
  12.   }  
  13.   return 0;  
  14. }  

【运行结果】

 

 

二、C++ STL中Map的按Value排序

 

        在第一部分中,我们借助map提供的参数接口,为它指定相应Compare类,就可以实现对map按Key排序,是在创建map并不断的向其中添加元素的过程中就会完成排序。

现在我们想要从map中得到学生按成绩的从低到高的次序输出,该如何实现呢?换句话说,该如何实现Map的按Value排序呢?

        第一反应是利用stl中提供的sort算法实现,这个想法是好的,不幸的是,sort算法有个限制,利用sort算法只能对序列容器进行排序,就是线性的(如vector,list,deque)。map也是一个集合容器,它里面存储的元素是pair,但是它不是线性存储的(前面提过,像红黑树),所以利用sort不能直接和map结合进行排序。

       虽然不能直接用sort对map进行排序,那么我们可不可以迂回一下,把map中的元素放到序列容器(如vector)中,然后再对这些元素进行排序呢?这个想法看似是可行的。要对序列容器中的元素进行排序,也有个必要条件:就是容器中的元素必须是可比较的,也就是实现了<操作的。那么我们现在就来看下map中的元素满足这个条件么?

       我们知道map中的元素类型为pair,具体定义如下:

 

  1. template <class T1, class T2> struct pair  
  2. {  
  3.   typedef T1 first_type;  
  4.   typedef T2 second_type;  
  5.   
  6.   T1 first;  
  7.   T2 second;  
  8.   pair() : first(T1()), second(T2()) {}  
  9.   pair(const T1& x, const T2& y) : first(x), second(y) {}  
  10.   template <class U, class V>  
  11.     pair (const pair &p) : first(p.first), second(p.second) { }  
  12. }  


pair也是一个模板类,这样就实现了良好的通用性。它仅有两个数据成员first 和 second,即 key 和 value,而且

 

头文件中,还为pair重载了 < 运算符, 具体实现如下: 

 

  1. template<class _T1, class _T2>  
  2.   inline bool  
  3.   operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)  
  4.   { return __x.first < __y.first  
  5.            || (!(__y.first < __x.first) && __x.second < __y.second); }  


重点看下其实现:

  1. __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second)  

 

这个less在两种情况下返回true,第一种情况:__x.first < __y.first  这个好理解,就是比较key,如果__x的key 小于 __y的key 则返回true。

第二种情况有点费解:  !(__y.first < __x.first) && __x.second < __y.second

当然由于||运算具有短路作用,即当前面的条件不满足是,才进行第二种情况的判断 。第一种情况__x.first < __y.first 不成立,即__x.first >= __y.first 成立,在这个条件下,我们来分析下  !(__y.first < __x.first)  && __x.second < __y.second

 !(__y.first < __x.first) ,看清出,这里是y的key不小于x的key ,结合前提条件,__x.first < __y.first 不成立,即x的key不小于y的key 

即:  !(__y.first < __x.first)  &&   !(__x.first < __y.first )   等价于   __x.first == __y.first ,也就是说,第二种情况是在key相等的情况下,比较两者的value(second)。

这里比较令人费解的地方就是,为什么不直接写 __x.first == __y.first 呢? 这么写看似费解,但其实也不无道理:前面讲过,作为map的key必须实现<操作符的重载,但是并不保证==符也被重载了,如果key没有提供==,那么 ,__x.first == __y.first 这样写就错了。由此可见,stl中的代码是相当严谨的,值得我们好好研读。

 现在我们知道了pair类重载了<符,但是它并不是按照value进行比较的,而是先对key进行比较,key相等时候才对value进行比较。显然不能满足我们按value进行排序的要求。

而且,既然pair已经重载了<符,而且我们不能修改其实现,又不能在外部重复实现重载<符。

 

  1. typedef pairint> PAIR;  
  2. bool operator< (const PAIR& lhs, const PAIR& rhs) {  
  3.     return lhs.second < rhs.second;  
  4. }  


如果pair类本身没有重载<符,那么我们按照上面的代码重载<符,是可以实现对pair的按value比较的。现在这样做不行了,甚至会出错(编译器不同,严格的就报错)。

 

那么我们如何实现对pair按value进行比较呢? 第一种:是最原始的方法,写一个比较函数;  第二种:刚才用到了,写一个函数对象。这两种方式实现起来都比较简单。

 

  1. typedef pairint> PAIR;  
  2.   
  3. bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {  
  4.   return lhs.second < rhs.second;  
  5. }  
  6.   
  7. struct CmpByValue {  
  8.   bool operator()(const PAIR& lhs, const PAIR& rhs) {  
  9.     return lhs.second < rhs.second;  
  10.   }  
  11. };  


接下来,我们看下sort算法,是不是也像map一样,可以让我们自己指定元素间如何进行比较呢?

 

 

  1. template <class RandomAccessIterator>  
  2.   void sort ( RandomAccessIterator first, RandomAccessIterator last );  
  3.   
  4. template <class RandomAccessIterator, class Compare>  
  5.   void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );  

我们看到,令人兴奋的是,sort算法和map一样,也可以让我们指定元素间如何进行比较,即指定Compare。需要注意的是,map是在定义时指定的,所以传参的时候直接传入函数对象的类名,就像指定key和value时指定的类型名一样;sort算法是在调用时指定的,需要传入一个对象,当然这个也简单,类名()就会调用构造函数生成对象。

 

这里也可以传入一个函数指针,就是把上面说的第一种方法的函数名传过来。(应该是存在函数指针到函数对象的转换,或者两者调用形式上是一致的,具体确切原因还不明白,希望知道的朋友给讲下,先谢谢了。)

【参考代码】

  1. int main() {  
  2.   mapint> name_score_map;  
  3.   name_score_map[“LiMin”] = 90;  
  4.   name_score_map[“ZiLinMi”] = 79;  
  5.   name_score_map[“BoB”] = 92;  
  6.   name_score_map.insert(make_pair(“Bing”,99));  
  7.   name_score_map.insert(make_pair(“Albert”,86));  
  8.  //把map中元素转存到vector中   
  9.   vector name_score_vec(name_score_map.begin(), name_score_map.end());  
  10.   sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());  
  11.  // sort(name_score_vec.begin(), name_score_vec.end(), cmp_by_value);  
  12.   for (int i = 0; i != name_score_vec.size(); ++i) {  
  13.     cout << name_score_vec[i] << endl;  
  14.   }  
  15.   return 0;  
  16. }  

【运行结果】

 

           原创文章,转载请注明: 转载自   IIcyZhao’s Road

 

          本文链接地址: http://blog.csdn.net/iicy266/article/details/11906189

 

poj 2492 A Bug’s Life (并查集)

http://poj.org/problem?id=2492

Hint

Huge input,scanf is recommended.
也是带种类的冰茶几。
由于只分了两类…我们还是可以按照上道题的做法。。
感觉完全是一样的题啊。。
结果一直WA。。。。
最后发现。。。我边读入边判断。。发现同性恋了就直接Break掉了。。。后面改组的数据读到下一组去了233,不WA就日了汪了。。。
还是把数据的读完再进行操作比较好==

poj 1703 Find them, Catch them (并查集)

http://poj.org/problem?id=1703
种类冰茶几…看到还有一种算是拓展的交加权冰茶几?
看到有做法是在开一个数组。。。记录是哪一组….
但是因为只有两组….我们可以分别存…
因为不知道每一个D的两个人分别是哪个组(帮派?)
可以都存一下。
TLE了两次….应该是用了cin的事。。。改成scanf就变WA了。。。
想了下。原来是我对“not sure yet”的判断出现失误。
我开了一个v数组,记录在D下出现的人。
我误以为出现的人的帮派一定是确定的。
实际上并不是。
比如 1,3 5,7 3和7都出现了。但是3和7是一组与否显然还是“not sure yet”

codeforces 535 C.Tavas and karafs (解方程)

http://codeforces.com/problemset/problem/535/C
题读了好几遍才读懂。
题意是给出一个等差数列,操作严格要求从最左边不为零的连续m个数减去1,最多执行t次后问离最左边最远的位置在哪里。
有两个限制条件…一个是本身的si不能大于t,否则无法吃完。
还有一个是从sl到sr的和不能超过m*t (比赛的时候考虑的不周到。。实际上只有当r-l+1比m大的时候才是m,也就是说要取min(m,l-r+1))
这题正解应该是二分….直接Lower_bound。。。看到也有人用前缀和搞的。
我是解方程了(貌似是个傻逼做法)….
可以列出一个关于r的一元二次方程。。。然后求根公式2333
方程是:

 

然后再和第一个条件得到的r比较取小的就是结果…..

等周末把这题的二分解法也写一些。

下面是蒟蒻傻逼的数学方恒解法的代码:

 

[WA]cf 534 D. Handshakes

D. Handshakes
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

On February, 30th n students came in the Center for Training Olympiad Programmers (CTOP) of the Berland State University. They came one by one, one after another. Each of them went in, and before sitting down at his desk, greeted with those who were present in the room by shaking hands. Each of the students who came in stayed in CTOP until the end of the day and never left.

At any time any three students could join together and start participating in a team contest, which lasted until the end of the day. The team did not distract from the contest for a minute, so when another student came in and greeted those who were present, he did not shake hands with the members of the contest writing team. Each team consisted of exactly three students, and each student could not become a member of more than one team. Different teams could start writing contest at different times.

Given how many present people shook the hands of each student, get a possible order in which the students could have come to CTOP. If such an order does not exist, then print that this is impossible.

Please note that some students could work independently until the end of the day, without participating in a team contest.

Input

The first line contains integer n (1 ≤ n ≤ 2·105) — the number of students who came to CTOP. The next line contains n integersa1, a2, …, an (0 ≤ ai < n), where ai is the number of students with who the i-th student shook hands.

Output

If the sought order of students exists, print in the first line “Possible” and in the second line print the permutation of the students’ numbers defining the order in which the students entered the center. Number i that stands to the left of number j in this permutation means that the i-th student came earlier than the j-th student. If there are multiple answers, print any of them.

If the sought order of students doesn’t exist, in a single line print “Impossible”.

Sample test(s)
input

output

input

output

input

output

Note

In the first sample from the statement the order of events could be as follows:

  • student 4 comes in (a4 = 0), he has no one to greet;
  • student 5 comes in (a5 = 1), he shakes hands with student 4;
  • student 1 comes in (a1 = 2), he shakes hands with two students (students 4, 5);
  • student 3 comes in (a3 = 3), he shakes hands with three students (students 4, 5, 1);
  • students 4, 5, 3 form a team and start writing a contest;
  • student 2 comes in (a2 = 1), he shakes hands with one student (number 1).

In the second sample from the statement the order of events could be as follows:

  • student 7 comes in (a7 = 0), he has nobody to greet;
  • student 5 comes in (a5 = 1), he shakes hands with student 7;
  • student 2 comes in (a2 = 2), he shakes hands with two students (students 7, 5);
  • students 7, 5, 2 form a team and start writing a contest;
  • student 1 comes in(a1 = 0), he has no one to greet (everyone is busy with the contest);
  • student 6 comes in (a6 = 1), he shakes hands with student 1;
  • student 8 comes in (a8 = 2), he shakes hands with two students (students 1, 6);
  • student 3 comes in (a3 = 3), he shakes hands with three students (students 1, 6, 8);
  • student 4 comes in (a4 = 4), he shakes hands with four students (students 1, 6, 8, 3);
  • students 8, 3, 4 form a team and start writing a contest;
  • student 9 comes in (a9 = 2), he shakes hands with two students (students 1, 6).

In the third sample from the statement the order of events is restored unambiguously:

  • student 1 comes in (a1 = 0), he has no one to greet;
  • student 3 comes in (or student 4) (a3 = a4 = 1), he shakes hands with student 1;
  • student 2 comes in (a2 = 2), he shakes hands with two students (students 1, 3 (or 4));
  • the remaining student 4 (or student 3), must shake one student’s hand (a3 = a4 = 1) but it is impossible as there are only two scenarios: either a team formed and he doesn’t greet anyone, or he greets all the three present people who work individually.

 

WA#37了。。。感觉思路没有问题呀…就是纯模拟。以后再看。

 

codeforces 534 C Polycarpus’ Dice

http://codeforces.com/problemset/problem/534/C

题意是说一共有N个骰子,第I个筛子一共有di面…现在知道这些骰子的点数之和,问对于每一个骰子不能取得值有多少个。

乍一看有点不明觉厉…稍微再想下,求取值范围即可。

先把所有di相加,得到所有骰子点数之和的最大值…然后点数之和的最小值当然就是N

对于每个骰子,将最大值和最小值减去这个骰子的对应数值…然后与总和A进行比较。

注意要开long long !!!

比赛的时候我明明写了typedef。。。结果后面还是忘记了。。。真是悲伤。

cf 534B. Covered Path

http://codeforces.com/problemset/problem/534/B

题意是说一辆车,每秒内的速度恒定…第I秒到第I+1秒的速度变化不超过D。初始速度为V1,末速度为V2,经过时间t,问最远能走多远。

策略就是尽可能加速…加到某个时间,如果在这个时间不开始减速就回不到V2了。

从后往前预处理下每秒钟能达到的最大速度(如果超过这个速度,将不能减回到V2)

cf 535B Tavas and SaDDas

B. Tavas and SaDDas
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Once again Tavas started eating coffee mix without water! Keione told him that it smells awful, but he didn’t stop doing that. That’s why Keione told his smart friend, SaDDas to punish him! SaDDas took Tavas’ headphones and told him: “If you solve the following problem, I’ll return it to you.”

The problem is:

You are given a lucky number nLucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

If we sort all lucky numbers in increasing order, what’s the 1-based index of n?

Tavas is not as smart as SaDDas, so he asked you to do him a favor and solve this problem so he can have his headphones back.

Input

The first and only line of input contains a lucky number n (1 ≤ n ≤ 109).

Output

Print the index of n among all lucky numbers.

Sample test(s)
input

output

input

output

input

output

 

 

题意是只由数字4和数字7组成的数称为lucky number。。。给出一个lucky number 问是第几个….

看数据,,10^9.。。打表打法好啊! 大概10S吧。。。出结果…

 

 

 

codeforces 534 A. Exam

A. Exam
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

An exam for n students will take place in a long and narrow room, so the students will sit in a line in some order. The teacher suspects that students with adjacent numbers (i and i + 1) always studied side by side and became friends and if they take an exam sitting next to each other, they will help each other for sure.

Your task is to choose the maximum number of students and make such an arrangement of students in the room that no two students with adjacent numbers sit side by side.

Input

A single line contains integer n (1 ≤ n ≤ 5000) — the number of students at an exam.

Output

In the first line print integer k — the maximum number of students who can be seated so that no two students with adjacent numbers sit next to each other.

In the second line print k distinct integers a1, a2, …, ak (1 ≤ ai ≤ n), where ai is the number of the student on the i-th position. The students on adjacent positions mustn’t have adjacent numbers. Formally, the following should be true: |ai - ai + 1| ≠ 1 for all i from 1 tok - 1.

If there are several possible answers, output any of them.

 

题意是有n个数(1..n),问构造一个最长的数列,使得相邻元素的差的绝对值不等于1.

1,2,3,4特判下。

剩下的直接先走奇数,后走偶数构造即可。

codeforces 479D. Long Jumps

http://codeforces.com/problemset/problem/479/D

题意是说有一把尺子,本身有一些刻度,然后需要测量x和y,问最少需要添加多少个刻度,如果需要,这些刻度分别添加在什么位置。

 

一开始没有看清题目,以为答案最多为4,但是发现,a[1]=0 a[n]=l这两个是确定的,所以答案最多为2,

而不会出现中间有两个刻度,无论是往前刻还是往后都会越界的情况。

先去看看已知的刻度里有没有直接满足的。

除此之外,如果在已知的刻度下无法测量x也无法测量y,我们还可以找找是否能有公用点使得只刻一个刻度就可以满足题意。公用点分两种情况,一种是在两个刻度之间,另一种是在两个刻度的同侧。

前一种没什么坑,后一种要判断是否越界!!!

如果在已知的刻度下能测量x或者能测量出y但不能同时测量的话,就没有必要找公用点。

 

还有就是查找的话如果线性找复杂度是O(n2),会TLE在第27个点。

我们用二分…

话说STL里竟然连二分查找也有。。。。简直orz。。。。真是省时省力。

 

代码:

codeforces 525 B. Pasha and String

http://codeforces.com/problemset/problem/525/B

codeforces 482 A. Diverse Permutation(构造)

C – C

Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

Permutationp is an ordered set of integers p1,   p2,   …,   pn, consisting of n distinct positive integers not larger than n. We’ll denote asn the length of permutation p1,   p2,   …,   pn.

Your task is to find such permutation p of length n, that the group of numbers |p1 - p2|, |p2 - p3|, …, |pn - 1 - pn| has exactly k distinct elements.

Input

The single line of the input contains two space-separated positive integers nk (1 ≤ k < n ≤ 105).

Output

Print n integers forming the permutation. If there are multiple answers, print any of them.

Sample Input

Input

Output

Input

Output

Input

Output

Hint

By |x| we denote the absolute value of number x.

 

 

题意是说找到找到一组n个由1..n组成的数列,且每个数字只出现一次

满足每相邻的两项的差的绝对值一共有k种。

 

找规律即可。不好描述,直接上代码吧。

codeforces 47 C. Exams

http://codeforces.com/problemset/problem/479/C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年02月22日 星期一 23时31分10秒
File Name :code/cf/problem/479C.cpp
************************************************ */
 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
 
#include <cmath>
 
using namespace std;
int n,ans;
const int N=1E4+5;
int a[N],b[N];
 
struct  Q
{int a,b;
}q[N];
 
bool cmp(Q x, Q y)
{
    if ( x.a<y.a) return true;
    if ( x.a==y.a &&x.b<y.b ) return true;
    return false;
}
 
int main()
{
    scanf("%d",&n);
    for ( int i = 1 ; i <= n ; i++ )
        scanf("%d %d",&q[i].a,&q[i].b);
    sort(q+1,q+n+1,cmp);
 
    ans=q[1].b;
    for ( int i = 2 ; i <= n; i++ )
    {
        if ( q[i].b>=ans )
            ans = q[i].b;
        else ans = q[i].a;
    }
    printf("%d\n",ans);
    return 0;
}
 
 
 

hdu 1160 FatMouse’s Speed (最长上升子序列)

FatMouse’s Speed

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10172    Accepted Submission(s): 4521
Special Judge

Problem Description
FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.
 

 

Input
Input contains data for a bunch of mice, one mouse per line, terminated by end of file.

The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.

Two mice may have the same weight, the same speed, or even the same weight and speed. 

 

 

Output
Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],…, m[n] then it must be the case that 

W[m[1]] < W[m[2]] < ... < W[m[n]] and  S[m[1]] > S[m[2]] > … > S[m[n]]

In order for the answer to be correct, n should be as large as possible.
All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one. 

 

 

Sample Input
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
 

 

Sample Output
4
4
5
9
7
 

 

Source
 

 

Recommend
Ignatius
 
先排序,然后求一个最长上升子序列。
第一次做记录路径的题,比较无力。
调了很久,后来调到样例都不对整个人都无奈了。
可能也是调了太久的缘故,整个人比较烦躁,也忘记了题目中的那句“如果有多组接那么任意输出一种”,结果白白浪费了好久。sad
还是不要浮躁。
 
AC代码:

hdu 1260 tickets

Tickets

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1408    Accepted Submission(s): 687

Problem Description
Jesus, what a great movie! Thousands of people are rushing to the cinema. However, this is really a tuff time for Joe who sells the film tickets. He is wandering when could he go back home as early as possible.
A good approach, reducing the total time of tickets selling, is let adjacent people buy tickets together. As the restriction of the Ticket Seller Machine, Joe can sell a single ticket or two adjacent tickets at a time.
Since you are the great JESUS, you know exactly how much time needed for every person to buy a single ticket or two tickets for him/her. Could you so kind to tell poor Joe at what time could he go back home as early as possible? If so, I guess Joe would full of appreciation for your help.
 

 

Input
There are N(1<=N<=10) different scenarios, each scenario consists of 3 lines:
1) An integer K(1<=K<=2000) representing the total number of people;
2) K integer numbers(0s<=Si<=25s) representing the time consumed to buy a ticket for each person;
3) (K-1) integer numbers(0s<=Di<=50s) representing the time needed for two adjacent people to buy two tickets together.
 

 

Output
For every scenario, please tell Joe at what time could he go back home as early as possible. Every day Joe started his work at 08:00:00 am. The format of time is HH:MM:SS am|pm.
 

 

Sample Input
2
2
20 25
40
1
8
 

 

Sample Output
08:00:40 am
08:00:08 am
 

 

Source
 

 

Recommend
JGShining   |   We have carefully selected several similar problems for you:  1257 1231 1074 1069 1159 
 
 
dp
状态转移方程为dp[i]=min(dp[i-1]+a[i],dp[i-2]+b[i])   dp[i]为第i个人买完票所花的最少时间。a[i]和b[i]分别为单独买票和两个人一起买票的时间。
因为调试语句没删掉和错把B[I]的下表认为是从1开始(实际应从2开始) WA了两发 3A