題目:http://codeforces.com/contest/767

吐槽：

這場的題目不太行啊，感覺B題麻煩的要死，CD都比B簡單。

A Snacktower

分析：簡單模擬一下即可。

B The Queue

題意：

排隊在窗口買票，營業時間是[ts,tf]，一個人辦理業務需要的時間都是t 現在知道了n個人去到達的時間f[i] 現在小明要去買票，小明到達的時間如果跟n個人中某人一樣，那么就在這些人后面排隊。 問小明什么時候去等待的時間最少。

分析：

C Garland

題意：

給一棵樹，每一個點有個權值v[i]，刪除2條邊，分成3棵樹，使得三棵樹的節點權值和相同。

分析：

dfs即可。

D Cartons of milk

題意：

小明有n盒牛奶， 超市里有m盒牛奶，牛奶都有保質期，小明必須在保質期之前喝完n盒牛奶，并且盡可能多的買一些牛奶。問最多買幾盒？

分析：

顯然是二分答案，買x盒牛奶（買牛奶的話肯定優先買保質期長的）。 然后判斷原來的n個加上買的x個，看看是否可以喝完。因為n個和x個都是有序的，所以加在一起的話是O（n）。 時間復雜度nlogn。

E Change-free

題意：

有個人現在去購物，需要在n天去購物，每天需要c[i]盧布，但是找每個盧布會對收銀員產生f[i]的消極影響，現在他有m個盧布，并且有無數的紙幣，一個紙幣可以兌換100個盧布（找零錢的話收銀員會心情不好）。問最少給收銀員產生消極影響的方案。

分析：

首先可以肯定的是第i天至少支付紙幣c[i]/100張，還需支付c[i]%100盧布。那么如果沒有足夠的盧布，肯定需要支付1張紙幣讓收銀員找零（這樣就會產生(100-c[i]%100)*f[i]的消極影響，得到100-c[i]%100個盧布。如果有足夠的盧布有2種選擇，一種是支付盧布，另一種是支付一張紙幣，讓他找錢，因為這樣可以把盧布留著后面用（有可能后面產生某個很大的消極影響）。 乍一看像是dp，但是要求方案，好像不行。 因為當前的抉擇需要考慮以后的，所以從后面貪心就可以了~~每次如果有足夠的盧布，就選擇當前會有消極影響最大的那個支付。 現在唯一剩下的問題就是怎么判斷有沒有足夠的盧布，這個可以預處理一下，先假設到i前面所有的都支付紙幣就是最多可以收集的盧布。