Home > Old Blog Posts > USACO 1.1.2 Greedy Gift Givers

USACO 1.1.2 Greedy Gift Givers



直接模拟即可。对人名的处理稍为麻烦。

对于名字的处理,可考虑

线性查找,总复杂度 O(n^3)

排序后二分查找(此处n值较小,用插入排序即可),总复杂度O(n^2+n^2logn)=O(n^2logn)

hash表存储 总复杂度 O(n^2) 但需要较多存储空间。

代码:

/*
ID: dementr1
PROG: gift1
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
struct newdata
{
string name;
int money;
} data[11];
int search(newdata a[],string b)
{
int i;
for(i=0;i<10;i++)
if(a[i].name==b) return i;
}
int main()
{
int num,i,q,k;
int send[11]={},have[11]={};
int peo;
string tmp;
ifstream fin(“gift1.in”);
ofstream fout(“gift1.out”);
fin>>num;
for(i=0;i<num;i++) fin>>data[i].name;
for(i=0;i<num;i++)
{
fin>>tmp;
int p=search(data,tmp);
fin>>data[p].money>>q;
string tmp1;
int j;
if(q!=0)
{
for(k=0;k<q;k++)
{
fin>>tmp1;
j=search(data,tmp1);
have[j]+=(int)(data[p].money/q);
}
send[p]=data[p].money-data[p].money%q;
}
}
for(i=0;i<num;i++)
fout<<data[i].name<<” “<<have[i]-send[i]<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: