Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
这个题我用C++交WA了九次,第十次用G++交就过了,我就觉得奇怪这么个水题怎么老是交不过去,, 我看了一下 discuss里面别人说的什么先排序再找个负数的人全给他, 其实我觉得这个题有一种更简单更直观的思路(正确性尚有待证明) 把所有的人都只跟第一个人(随便选一个作为第一号人)扯上关系 刚开始与第一个人有关系的就不用说了, 假如有a b c d e几个人, b欠c 100 d欠e 50 那么可以这样,让b欠a 100 再a欠c 100 同样,让d欠a 50 再让a欠e 50 这样在读入的时候就边处理,最后,后面所有的人都只与a有债务关系,他们互相之间就没有任何关系,输出来的肯定是n-1种! 具体实现,只需用一个数组m[j] j是从2到n,表示第j个人欠第一个m[j]块钱,若为负则是第一个 人欠他的钱,在进行t项操作的过程中若j欠k 100 则m[j]+=100 m[k]-=100; 当然中间再加写 一个小函数找出s1,s2分别是第几号人, 最后从2到n输出m[j]便可!!! Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator