A-链接：https://www.nowcoder.com/acm/contest/133/A
来源：牛客网
输入包括若干行i
第一行包括一个数n，表示这棵树有n个节点
第二行包括n个数，第i个数表示第i个节点的颜色col
**注意：一个颜色的标号即价值
输出包括一行
第一行包括一个数，表示最小代价
12
边的输入根本就是多余的，直接枚举所有颜色统计最小的值即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define inf 0x3f3f3f3f3f3f3f 5 int col[100010]; 6 map<int,int>M; 7 int main(){ 8 int n,m,i,j,k; 9 while(cin>>n){ll u,v,tot=0,all=0; 10 M.clear(); 11 for(i=1;i<=n;++i) { 12 scanf("%d",col+i); 13 all+=col[i]; 14 M[col[i]]++; 15 } 16 for(i=1;i<n;++i){ 17 scanf("%d%d",&u,&v); 18 } 19 ll ans=inf; 20 for(i=1;i<=n;++i){ 21 ll tt=M[col[i]]; 22 ans=min(ans,((ll)n-tt)*col[i]+all-tt*col[i]); 23 } 24 cout<<ans<<endl; 25 } 26 return 0; 27 }
B-链接：https://www.nowcoder.com/acm/contest/133/B
来源：牛客网
第一行三个数v, n, m，分别代表背包容量，物品数量以及需要取出的物品数量
仅一行，代表最大的中位数
非常操蛋，因为我把m打成了n，把first打成了second导致debug了一天，浪费很久的时间= =
做法并不难想，将物品分成前，中，后三个部分且每一部分的长度都知道，然后预处理下前/后最小的体积值，
枚举中间的1/2个点，对于奇数长度，直接枚举中点。偶数长度，枚举第一个点，二分查找右边一个的点（之所以能二分是因为first递增
而且rs[]也是递增的），在满足总的体积不超v的情况下使得价值尽可能的大，也就等价于尽可能的找右边的点。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define pii pair<LL,LL> 5 6 pii x[100110]; 7 LL ls[100110],rs[100110]; 8 priority_queue<LL>q; 9 priority_queue<LL>q2; 10 11 void init(int n,int m){ 12 13 int ll=(m-1)/2,rr=(m-1)/2; 14 LL sum=0; 15 for(int i=1;i<=ll;++i){ 16 q.push(x[i].second); 17 sum+=x[i].second; 18 } 19 ls[ll]=sum; 20 for(int i=1+ll;i<=n;++i){ 21 if(q.empty()) continue; 22 if(/*!q.empty()&&*/q.top()>x[i].second){ 23 sum=sum-q.top()+x[i].second; 24 q.pop(); 25 q.push(x[i].second); 26 } 27 ls[i]=sum; 28 } 29 30 sum=0; 31 for(int i=n;i>n-rr;--i){ 32 q2.push(x[i].second); 33 sum+=x[i].second; 34 } 35 rs[n-rr+1]=sum; 36 for(int i=n-rr;i>=1;--i){ 37 if(!q2.empty()&&q2.top()>x[i].second){ 38 sum=sum-q2.top()+x[i].second; 39 q2.pop(); 40 q2.push(x[i].second); 41 } 42 rs[i]=sum; 43 } 44 } 45 int main(){ 46 int n,m,i,j,k; 47 LL v; 48 cin>>v>>n>>m; 49 for(i=1;i<=n;++i) scanf("%lld%lld",&x[i].first,&x[i].second); 50 sort(x+1,x+1+n); 51 init(n,m); 52 int ll=(m-1)/2,rr=(m-1)/2; 53 if(m%2){ 54 LL ans=0; 55 for(i=n-rr;i>ll;--i){ 56 if(ls[i-1]+rs[i+1]+x[i].second<=v) 57 {ans=x[i].first;break;} 58 } 59 cout<<ans<<endl; 60 } 61 else{ 62 LL ans=0; 63 for(i=ll+1;i<n-rr;++i){ 64 int L=i+1,R=n; 65 LL tmp=v-ls[i-1]-x[i].second; 66 while(L<R){ 67 int mid=R-((R-L)>>1); 68 if(n-(mid+1)+1>=rr&&x[mid].second+rs[mid+1]<=tmp) L=mid; 69 else R=mid-1; 70 } 71 if(tmp-x[L].second-rs[L+1]>=0&&n-(L+1)+1>=rr) 72 ans=max(ans,x[i].first+x[L].first); 73 } 74 cout<<ans/2<<endl; 75 } 76 77 return 0; 78 }
原文：https://www.cnblogs.com/zzqc/p/9347500.html