随笔-141  评论-9  文章-3  trackbacks-0
USACO 1.1.2 Greedy Gift Givers
题意：每个人都准备一些钱平均分给其他人，不能分的部分留给自己，计算每个人的得失。

分析：使用两个数组，一个计算得，一个计算失，result[i] = receive[i] - give[i]

PS: 用Map更简单些。

/*
ID: lorelei3
PROG: gift1
LANG:C++
*/

#include <fstream>
#include <string>

using namespace std;

const int NP = 15;

string names[NP];
int recieved[NP];
int gived[NP];
int np;

inline int  find(string s){
    for(int i=0; i<np; ++i)
        if(s == names[i])
            return i;
    return -1;
}

int main(){

    //init
    int i;
    ifstream in("gift1.in");
    ofstream out("gift1.out");
    in>>np;
    for(i=0; i<np; i++)
        in>>names[i];

    //solve
    for(i=0; i<np; i++){
        string name;
        int sum ,n;
        in>>name>>sum>>n;
        if(n==0)
            continue;
        int give = sum/n, stay = sum%n;
        int loc = find(name);
        recieved[loc] += stay;
        gived[loc] += sum;
        for(int j=0; j<n; ++j){
            in>>name;
            recieved[find(name)] += give;
        }
    }
    
    //output
    for(i=0; i<np; ++i)
        out<<names[i]<<" "<<recieved[i] - gived[i]<<endl;

    return 0;
}
posted on 2010-11-02 22:09 小阮 阅读(196) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮