首页 > 技术文章 > AcWing 1800. 不做最后一个! 活用map和vector

ZheyuHarry 2022-04-05 13:40 原文

 

 

 

 

 

分析:通过读题我们可以知道,这道题其实并不是什么很困难的题,无非就是让我们找到当前产奶量倒数第二小的奶牛,并且特判一下有多头奶牛满足或者没有奶牛满足的情况罢了,这道题的关键在于我们应该如何去分析数据,首先我们知道这里的挤奶记录不是把名字相同的奶牛给综合了,所以我们要想得到对应的奶牛的产奶的数量最简单的方法就是使用unordered_map,但是如果我们想对数据进行从小到大的排序就不方便,所以我就将map里面的东西转到vector中,然后对vector的内容进行排序即可,接下来我们就要去寻找倒数第二小的牛,我们定义一个it指针初始化位0,只有当所有的牛都能挤奶的情况下,我们让it指针前进到第一个大于最小产奶量的牛的位置上,如果有些牛不产奶,指针就会指在0的位置,我们只需要判断当前情况下如果只有一头牛在vector中或者有多头牛而且it和it+1的牛产奶量不相同的时候,我们就可以放心的输出it对应的奶牛的名字;不然的话我们统一输出Tie:

 

代码:

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;
typedef pair<int,string> PSI;

int main()
{
int n;
cin >> n;
vector<PSI> v;
unordered_map<string,int> mp;
while (n -- )
{
string s;
int a;
cin >> s >> a;
mp[s]+=a;
}
for(pair<string,int> t : mp){
v.push_back({t.y,t.x});
}
sort(v.begin(),v.end());
int it = 0;
if(v.size() == 7){
while(it < v.size() && v[it].x == v[0].x) it++;
}
if(it < v.size() && (v.size() == 1 || v[it].x != v[it+1].x))
cout << v[it].y << '\n';
else cout << "Tie" << '\n';
return 0;
}

 

总结:这道题的关键点在于提醒我们不要遇到这种问题就去设置mini,而是用指针的操作来定位大小,并且这里map转vector的方式也值得一学!

推荐阅读