- Shopping
- Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
- Total Submission(s): 6348 Accepted Submission(s): 2215
- Problem Description
- Every girl likes shopping,so does dandelion.Now she finds the shop is increasing the price every day because the Spring Festival is coming .She is fond of a shop which is called "memory". Now she wants to know the rank of this shop's price after the change of everyday.
- Input
- One line contians a number n ( n<=10000),stands for the number of shops.
- Then n lines ,each line contains a string (the length is short than 31 and only contains lowercase letters and capital letters.)stands for the name of the shop.
- Then a line contians a number m (1<=m<=50),stands for the days .
- Then m parts , every parts contians n lines , each line contians a number s and a string p ,stands for this day ,the shop p 's price has increased s.
- Output
- Contains m lines ,In the ith line print a number of the shop "memory" 's rank after the ith day. We define the rank as :If there are t shops' price is higher than the "memory" , than its rank is t+1.
- Sample Input
- 3
- memory
- kfc
- wind
- 2
- 49 memory
- 49 kfc
- 48 wind
- 80 kfc
- 85 wind
- 83 memory
- Sample Output
- 1
- 2
理解题意:
这个题的题意很明确, 让输出 "memory" 这个商店每天的价格排名
解题思路:
首先, map 是关联容器, 他可以实现从键值到值的映射, 类似函数中的一一对应; 然后我们定义一个 map<string,int>shop; 用来存储商店的名字和每天的价格; 注意给每个商店赋值价格的操作是 shop[s] += p; 但是如果用下面这种方法进行排名的话, 时间就会超限
- int rank = 1;
- map<string,int>::iterator it;
- for(it = shop.begin();it != shop.end(); it++){
- if(it->second>shop["memory"])
- rank++;
- }
- cout<<rank<<endl;
所以我经过查阅资料发现了另一种方法, 用一个数组来把价格存起来, 然后用 sort 排序后, 再通过比较数组中的值是否和 "memory" 商店的价格相等来输出他的位置, 即为他的排名
- #include <iostream>
- #include <string>
- #include <map>
- #include <algorithm>
- using namespace std;
- bool my_camp(int x,int y){
- return x>y;
- }
- int main()
- {
- int n,m,p;
- int a[10001];
- map<string,int>shop;
- while(cin>>n){
- string s;
- for(int i = 1;i <= n; i++)
- cin>>s;
- cin>>m;
- while(m--){
- for(int i = 1;i <= n; i++){
- cin>>p>>s;
- shop[s] += p;
- a[i] = shop[s];
- }
- /*int rank = 1;
- map<string,int>::iterator it;
- for(it = shop.begin();it != shop.end(); it++){
- if(it->second>shop["memory"])
- rank++;
- }
- cout<<rank<<endl; */
- sort(a+1,a+n+1,my_camp);
- for(int i = 1;i <= n; i++){
- if(a[i] == shop["memory"]){
- cout<<i<<endl;
- break;
- }
- }
- }
- shop.clear();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3399734.html