題目原文請看這里：
Greedy Gift Givers 題目本比較簡單，但我讀了半天才算讀懂，英文水平跟不上了。
題目大意：有NP個人，每個人都向其他人送錢，同時他又會收到別人送給他的錢。題目要求計算每個人收到的錢比送出的錢多多少。
解答：
/*
ID: lixianm1
PROG: gift1
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cassert>
typedef std::vector<std::string> StrVector;
struct Person
{
std::string name; // name
int money_send; // money for sending
int money_receive; // money received
StrVector receiver; // all receivers
Person()
{
money_send = 0;
money_receive = 0;
}
};
typedef std::map<std::string, Person> PersonMap;
int main(int argc, char* argv[])
{
//////////////////////////////////////////////////////////////////////////open the file
std::string strInFile = "gift1.in";
std::string strOutFile = "gift1.out";
std::ifstream fin(strInFile.c_str());
std::ofstream fout(strOutFile.c_str());
if (!fin)
{
std::cout<<"failed to open file for read"<<std::endl;
return 1;
}
if (!fout)
{
std::cout<<"failed to open file for write"<<std::endl;
fin.close();
return 1;
}
//////////////////////////////////////////////////////////////////////////read file and init all variables
int nPersonNum;
PersonMap mPerson;
StrVector vPersonName;
fin>>nPersonNum;
assert(nPersonNum>0);
for(int i=0; i<nPersonNum; ++i)
{
Person person;
fin>>person.name;
mPerson[person.name]= person;
vPersonName.push_back(person.name);
}
std::string strName;
while(fin>>strName)
{
fin>>mPerson[strName].money_send;
int nReceiver;
fin>>nReceiver;
std::string strReceiverName;
for (int i=0; i<nReceiver; ++i)
{
fin>>strReceiverName;
mPerson[strName].receiver.push_back(strReceiverName);
}
}
//////////////////////////////////////////////////////////////////////////process
for (PersonMap::iterator iter= mPerson.begin(); mPerson.end()!=iter; ++iter)
{
Person& person = iter->second;
int nReceiverNum = person.receiver.size();
if ((0!=nReceiverNum))
{
int nMoneySend = person.money_send/nReceiverNum;
for (int i=0; i<nReceiverNum; ++i)
{
mPerson[person.receiver[i]].money_receive+= nMoneySend;
}
person.money_send = nMoneySend*nReceiverNum;
}
}
//////////////////////////////////////////////////////////////////////////write the process result
for (StrVector::iterator iter= vPersonName.begin(); vPersonName.end()!=iter; ++iter)
{
fout<<*iter<<" "<<mPerson[*iter].money_receive-mPerson[*iter].money_send<<std::endl;
}
//////////////////////////////////////////////////////////////////////////end and exit
fin.close();
fout.close();
//system("pause");
return 0;
}