Timus #1650. Billionaires

题目:有n个富豪(数据包含:姓名,开始时的所在地,拥有财富),某地财富即为在此的所有富豪财富相加。在接下来的m天,会有k个土豪在某一天晚上离开所在地,在第二天早上到达所在地。求每天拥有财富最多的城市,按照字母表顺序输出某城市财富最多的天数。ps:若某一天有两个及以上的城市财富相同则该天不算在这几个城市的天数中,若最终有城市天数为0则不输出此城市。

解析:该题目逻辑很简单,建立Person和City结构体,Person储存姓名,所在地,财富;City储存城市名,拥有财富。循环查找/插入/删除/更新City和Person中的数据,并找到City中财富最大的城市。

代码分析:你必须建立map或set容器或写自己的Tree结构来完成此题,否则必会超时。比如,如果你用顺序的方式遍历City中最大的城市/城市名必定会超时。
1. 我的解决方法是用map<string, City*>cityptr;用指针快速修改和查找。
2. 更加快捷的方式是map<string, pair<City*, long long>>Person;
3. 傻一点的方法是建立map<string, int>index;这种方法缺点是每次都要更新index。

发表评论

您的电子邮箱地址不会被公开。

浙ICP备2021019730-1    浙公网安备 33010902002953号
Copyright © 2022 PanCake