Timus #1650. Billionaires – Pancake's Personal Website

题目：有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。

#include<iostream>
#include<map>
#include<set>
using namespace std;

struct City {
	string name;
	long long money;
	City(string nameIN, long long moneyIN):name(nameIN),money(moneyIN) {}
	bool operator< (const City& a)const
	{
		if (this->money == a.money) return this->name < a.name;
		return this->money > a.money;
	}
};

void add(set<City>& city, map<string, City*>& cityptr, string cityname, long long money) {
	map<string, City*>::iterator ptr;
	ptr = cityptr.find(cityname);
	City * cityNow = new City(cityname, money);
	if(ptr == cityptr.end()){
		city.insert(*cityNow);
		cityptr.insert({ cityNow->name, cityNow });
	}
	else {
		cityNow->money += ptr->second->money;
		city.erase(*ptr->second);
		ptr->second = cityNow;
		city.insert(*cityNow);
	}

}

void insertResult(set<City>& city, map<string, int> &result, int day) {
	string name;
	if (city.size() >= 2) {
		set<City>::iterator ptr = city.begin();
		if (ptr->money - (++ptr)->money != 0) name = city.begin()->name;
		else return;
	}
	else if (city.size() == 0) return;
	else if (city.size() == 1) name = city.begin()->name;
	map<string, int>::iterator ptr;
	ptr = result.find(name);
	if (ptr != result.end()) ptr->second += day;
	else result.insert({ name, day });
}


void del(set<City>& city, map<string, City*>& cityptr, string cityName, long long money) {
	map<string, City*>::iterator ptr;
	ptr = cityptr.find(cityName);
	City *tempCity = new City(cityName, ptr->second->money - money);
	city.erase(*ptr->second);
	delete ptr->second;
	ptr->second = tempCity;
	if (tempCity->money == 0) {
		cityptr.erase(ptr);
		return;
	}
	city.insert(*tempCity);
}

int main() {
	map<string, pair<string, long long>>Person;
	map<string, int>result;
	map<string, City*>cityptr;
	set<City>city;
	int n, m, k, day = 0, preday;
	cin >> n;
	string namePerson;
	string nameCity;
	string namePreCity;
	long long money;
	for (int i = 0; i < n; i++) {
		cin >> namePerson >> nameCity >> money;
		Person.insert({ namePerson,make_pair(nameCity,money) });
		add(city, cityptr, nameCity, money);
	}
	cin >> m >> k;
	for (int i = 0; i < k; i++) {
		preday = day;
		cin >> day >> namePerson >> nameCity;
		insertResult(city, result, day - preday);
		map<string, pair<string, long long>>::iterator ptr;
		ptr = Person.find(namePerson);
		money = ptr->second.second;
		add(city, cityptr, nameCity, money);
		namePreCity = ptr->second.first;
		ptr->second.first = nameCity;
		del(city, cityptr, namePreCity, money);
	}
	insertResult(city, result, m - day);
	for (auto i : result) {
		if (i.second == 0)continue;
		cout << i.first << " " << i.second << endl;
	}
}

#include<iostream>

#include<map>

#include<set>

using namespace std;

struct City {

string name;

long long money;

City(string nameIN, long long moneyIN):name(nameIN),money(moneyIN) {}

bool operator< (const City& a)const

{

if (this->money == a.money) return this->name < a.name;

return this->money > a.money;

}

};

void add(set<City>& city, map<string, City*>& cityptr, string cityname, long long money) {

map<string, City*>::iterator ptr;

ptr = cityptr.find(cityname);

City * cityNow = new City(cityname, money);

if(ptr == cityptr.end()){

city.insert(*cityNow);

cityptr.insert({ cityNow->name, cityNow });

}

else {

cityNow->money += ptr->second->money;

city.erase(*ptr->second);

ptr->second = cityNow;

city.insert(*cityNow);

}

void insertResult(set<City>& city, map<string, int> &result, int day) {

string name;

if (city.size() >= 2) {

set<City>::iterator ptr = city.begin();

if (ptr->money - (++ptr)->money != 0) name = city.begin()->name;

else return;

}

else if (city.size() == 0) return;

else if (city.size() == 1) name = city.begin()->name;

map<string, int>::iterator ptr;

ptr = result.find(name);

if (ptr != result.end()) ptr->second += day;

else result.insert({ name, day });

}

void del(set<City>& city, map<string, City*>& cityptr, string cityName, long long money) {

map<string, City*>::iterator ptr;

ptr = cityptr.find(cityName);

City *tempCity = new City(cityName, ptr->second->money - money);

city.erase(*ptr->second);

delete ptr->second;

ptr->second = tempCity;

if (tempCity->money == 0) {

cityptr.erase(ptr);

return;

}

city.insert(*tempCity);

}

int main() {

map<string, pair<string, long long>>Person;

map<string, int>result;

map<string, City*>cityptr;

set<City>city;

int n, m, k, day = 0, preday;

cin >> n;

string namePerson;

string nameCity;

string namePreCity;

long long money;

for (int i = 0; i < n; i++) {

cin >> namePerson >> nameCity >> money;

Person.insert({ namePerson,make_pair(nameCity,money) });

add(city, cityptr, nameCity, money);

}

cin >> m >> k;

for (int i = 0; i < k; i++) {

preday = day;

cin >> day >> namePerson >> nameCity;

insertResult(city, result, day - preday);

map<string, pair<string, long long>>::iterator ptr;

ptr = Person.find(namePerson);

money = ptr->second.second;

add(city, cityptr, nameCity, money);

namePreCity = ptr->second.first;

ptr->second.first = nameCity;

del(city, cityptr, namePreCity, money);

}

insertResult(city, result, m - day);

for (auto i : result) {

if (i.second == 0)continue;

cout << i.first << " " << i.second << endl;

}

发表回复 取消回复

发表回复取消回复