python3刷USACO题库 1.2.2 Greedy Gift Givers

in #acm7 years ago (edited)

这个仍然是基础语言题目。题目内容很简单,大致是一组朋友互相赠红包,每个人可能赠出,也可能收到,经过几轮之后,打印出最终每个人的余额。

对于python3来说,字典这个数据结构,很适合这个问题,所以首先要学一下字典相关的操作。然后是python3和python2关于字典的一个小坑以及文件读取函数的一个小坑,

字典

字典是一种可变容器模型,由很多组键值(key-value)对组成。其中key是创立后不能改变的,而value是可以随时修改的。key由不能改变的数据类型构成,如字符串,数字,元组等;而value可以是任何数据类型,可以是单个数值变量,也可以是数组等。key不能重复定义,否则会保留最后一个。

涉及的简单操作,包括创建:

dict1 = { 'apple': 1 };
dict2 = { 'banana': 2,  'orange': 3 };

修改:

dict = {'apple': 1}
dict['apple'] =2               (update)
dict['banana'] = 3          (add new member)

删除:

dict = {'apple': 1, 'banana': 2, 'orange': 3}
del dict['apple']                         # 删除键 'apple'
dict.clear()                                   # 清空字典
del dict                                          # 删除字典

其他内置操作:

计算字典元素总个数,即键的总数

len(dict)
3

输出字典:

str(dict)
{'apple':1, 'banana':2, 'orange':3}


只输出所有的keys:

dict.keys()
['apple', 'banana', 'orange']

dict.values()
[1,2,3]

dict.items()
{'apple':1, 'banana':2, 'orange':3}

检测某键是否存在:

if  'Age' in dict:
    print("键 Age 存在")
else :
    print("键 Age 不存在")

python3遍历字典:

for key, value in mydic.items() :
    print (key, value)

曾经在python2里,存在一个mydic.iteritems()的方法,但python3已经去掉了。

几个小坑

在这个题目里,有个要求,即最后打印每个人的余额时,需要按照最初给出组成员的顺序打印。对于python3.6版本,这个不成问题,因为python3.6的一个改动,即字典默认的排序是按照添加成员的顺序。而在python3.6以前的版本,这个是没有的。我的编译器是python3.6.2因此,默认是会给出正确的顺序。然而USACO的裁判机上估计是以前版本的python3,因此不能给出正确的结果。为了在python3.6以前,也能一样给出正确的结果,需要使用:

from collections import OrderedDict
dict=OrderedDict()

所以,我因为这个版本问题,在 本地上是正确输出,而到了OJ上则显示有错误。

另一个小坑是关于文件读取函数readline(),readlines()。默认这些函数会在读取的数据最后加上一个换行符。因此如果直接把通过readline()读取的人名放到字典里作为Key,实际上这些人名最后还多出来一个换行符。这样在最后打印结果的时候,就会连换行符一起打印出来。这样不符合题目要求的格式了(题目要求人名和余额在同一行)。所以需要strip方法来去掉多出的换行符:

fin = open ('gift1.in', 'r')
dict[fin.readline().strip('\n')]=0

我的python3程序:

from collections import OrderedDict

fin = open ('gift1.in', 'r')
fout = open ('gift1.out', 'w')

dict=OrderedDict()
No_of_people=int(fin.readline())
for i in range(0, No_of_people):
    dict[fin.readline().strip('\n')]=0
    
    
    
while True:
    Person_send_out=fin.readline().strip('\n')
    print(Person_send_out+'\n')
    if Person_send_out=='':
        break
    
    send_out=fin.readline().strip('\n')


    Total_to_send=int(send_out.split(' ')[0])
    No_of_portion=int(send_out.split(' ')[1])
    
    print("{}".format(Total_to_send))
    print("{}".format(No_of_portion))
    
    
    
    if (Total_to_send==0):
        Each_portion=0
        left_over=0
    else:
        Each_portion=Total_to_send//No_of_portion
        left_over=Total_to_send%No_of_portion
    
    
    print("{}".format(Each_portion))
    print("{}".format(left_over))    
    
    
    for i in range(0, No_of_portion):
        name1 = fin.readline().strip('\n')
        dict[name1] = dict[name1] + Each_portion
        
    dict[Person_send_out]= dict[Person_send_out] - Total_to_send + left_over
    

    
for k,v in dict.items(): 
        fout.write (k+' ')
        fout.write (str(v)+'\n')
        print (k,v)
        
fout.close()

参考资料:

  1. https://stackoverflow.com/questions/39980323/are-dictionaries-ordered-in-python-3-6
  2. https://www.blog.pythonlibrary.org/2017/03/15/python-101-all-about-dictionaries/
  3. https://jianpengzhang.github.io/2017/02/26/2017022604/
  4. http://blog.csdn.net/jfkidear/article/details/7532293

Coin Marketplace

STEEM 0.26
TRX 0.20
JST 0.038
BTC 96270.61
ETH 3631.10
USDT 1.00
SBD 3.88