problem Mashmokh and Water Tanks
题目大意
给你一棵树，k升水，p块钱，进行一次游戏。
在游戏进行前，可以在任意个节点上放置1升水（总数不超过k）
游戏进行若干轮，每轮游戏开放所有节点，可以选择若干个节点关闭，代价为该节点的水数量。然后所有未关闭的节点的水流向它的父亲(不会连续移动)。最后，根节点中的水会被取走，水的数量为该轮游戏的盈利。
求盈利最大的某轮游戏的盈利。
解题分析
在放置水的选择上，应该尽量选择深度相邻的节点，即将所有节点按照深度排序后，所选择放水的节点应该是连续的一段。
考虑选择某段区间后，所需要花费的钱。
假设深度范围为 [l , r] ，某个深度的点为 a[i] ，则花费钱为sigma(a[i]*(r-i))
用两个指针进行扫描即可。
参考程序
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17 18 #define V 100008 19 #define E 200008 20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m,r+1,rt<<1|1 23 #define clr(x,v) memset(x,v,sizeof(x)); 24 25 const int mo = 1000000007; 26 const int inf = 0x3f3f3f3f; 27 const int INF = 2000000000; 28 /**************************************************************************/ 29 30 int n,water,coin,d; 31 int h[V]; 32 33 struct line{ 34 int u,v,nt; 35 }eg[E]; 36 int lt[V],sum; 37 38 void add(int u,int v){ 39 eg[++sum]=(line){u,v,lt[u]}; lt[u]=sum; 40 } 41 42 void dfs(int u,int fa,int dep){ 43 h[u]=dep; 44 for (int i=lt[u];i;i=eg[i].nt){ 45 int v=eg[i].v; 46 if (v!=fa) dfs(v,u,dep+1); 47 } 48 } 49 50 int main(){ 51 clr(lt,0); sum=1; 52 scanf("%d %d %d",&n,&water,&coin); 53 for (int i=1;i<n;i++){ 54 int u,v; 55 scanf("%d %d",&u,&v); 56 add(u,v); 57 add(v,u); 58 } 59 dfs(1,0,1); 60 sort(h+1,h+n+1); 61 int i=2,j=2,ans=1; 62 long long cost=0; 63 while (i<n && j<n){ 64 j++; 65 if (h[j]!=h[j-1]) cost+=j-i; 66 while (cost>coin){ 67 cost-=h[j]-h[i]; 68 i++; 69 } 70 ans=max(ans,j-i+1); 71 } 72 printf("%d ",min(ans,water)); 73 }