@TryMyEdge
2017-01-31T08:20:59.000000Z
字数 8670
阅读 792
题解
A Moo University - Financial Aid
题目大意：
有F(0<=F<=2*10^9)用于资助N(1<=N<=19999，N为奇数)头奶牛，有C(N<=C<=100000)头备选，第i头奶牛的成绩为Si(1<=Si<=2*10^9)，需要资助的金额为Ai(0<=Ai<=100000)。求这些资助的奶牛的成绩中位数最大是多少。
解题思路：
先将所有的奶牛按照资助金额低优先、资助金额相同成绩高优先排序，选取前N头奶牛计算成绩中位数及总资助金额，总资助金额超过F的肯定无法资助。然后将这N头奶牛按照成绩的高低分别装入两个优先队列PQ1和PQ2中，成绩低的N/2头奶牛装入PQ1，成绩高的剩下(N+1)/2头奶牛装入PQ2。PQ1中资助金额高的在前，PQ2中成绩低的在前、成绩相同的资助金额高的在前。于是PQ1的队首表示前一半奶牛中资助金额最大的，PQ2的队首表示当前资助方案中的出于成绩中位数的资助金额最大的奶牛。
扫描剩下的奶牛，如果当前奶牛的成绩优于中位数，并且用他替换PQ1或PQ2的队首后总金额不超过F，那么把PQ2的队首从PQ2中移除后加入PQ1并去掉当前PQ1中资助金额最大的，把当前奶牛加入PQ2，维护一下当前的中位数和两个优先队列的队首。
小细节：注意处理不能资助的情况。新奶牛替换的不一定是PQ2中的奶牛，也可能是PQ1中的。
时间复杂度o(C*log(N))，空间复杂度o(N)。
AC代码：
#include<iostream>#include<cstdio>#include<algorithm>#include<queue>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007struct Per{int no,sco;int ned;}p[100005],temp1,temp2;bool cmp1(Per x1,Per x2){if(x1.ned==x2.ned)return x1.sco>x2.sco;elsereturn x1.ned<x2.ned;}bool cmp2(Per x1,Per x2){return x1.sco<x2.sco;}struct cmp3{bool operator ()(Per x1,Per x2){if(x1.sco==x2.sco)return x1.ned<x2.ned;elsereturn x1.sco>x2.sco;}};struct cmp4{bool operator ()(Per x1,Per x2){return x1.ned<x2.ned;}};int sum;int ans;pq <Per,vector<Per>,cmp4> q1;pq <Per,vector<Per>,cmp3> q2;int main(){int n,c;int f;cin>>c>>n>>f;sum=0;ans=-1;for(int i=0;i<n;i++){p[i].no=i;scanf("%d%lld",&p[i].sco,&p[i].ned);}sort(p,p+n,cmp1);sort(p,p+c,cmp2);for(int i=0;i<c;i++)sum+=p[i].ned;if(sum<=f){ans=p[c/2].sco;for(int i=0;i<c/2;i++)q1.push(p[i]);for(int i=c/2;i<c;i++)q2.push(p[i]);temp1=q1.top();temp2=q2.top();for(int i=c;i<n;i++){if(p[i].sco>temp2.sco && sum-max(temp1.ned,temp2.ned)+p[i].ned<=f){q1.push(temp2);q1.pop();sum=sum-max(temp1.ned,temp2.ned)+p[i].ned;q2.pop();q2.push(p[i]);temp1=q1.top();temp2=q2.top();ans=temp2.sco;}}}printf("%d\n",ans);return 0;}
B Sockets
题目大意：
n(1<=n<=200000)台电脑，m(1<=m<=200000)个插座，第i台电脑的工作电压为Pi(1<=Pi<=10^9)，第i个插座提供的电压为Si(1<=Si<=10^9)。有无限个转接器，插座使用一个转接器后提供的电压降为一半(向上取整)。求有多少台电脑能够得到合适的电源，此时最少用多少转接器，以及插座和电脑的配对情况。
解题思路：
当前提供最高电压的插座和等于当前工作电压最高的电脑电压相等，那么一定会产生一对匹配。如果高于，那么当前插座会接上一个转接器备用。如果低于，那么这台电脑就没有插座能匹配了。由此我们记录每个插座当前提供的电压和已经接上的转接器个数，然后装入优先队列，优先队列中电压高优先，电压相等转接器接的少的优先。然后将电脑安装工作电压从高到低排序，对于每一台电脑，如果队首的插座和当前电脑电压相同则配对，大于则出队后接上转接器再入队，小于则当前电脑无法匹配，跳至下一台电脑。
小细节：处理好配对的输出。插座电压相同时转接器接的少的要优先。
时间复杂度o(m*log(Si))，空间复杂度o(n+m)。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007struct Soc{int no,times,val;friend bool operator <(Soc x1,Soc x2){if(x1.val==x2.val)return x1.times>x2.times;elsereturn x1.val<x2.val;}}s[200005],temp;struct Com{int no,ans,val;}c[200005];pq <Soc> q;bool cmp1(Com x1,Com x2){return x1.val>x2.val;}bool cmp2(Com x1,Com x2){return x1.no<x2.no;}int main(){int ans1=0,ans2=0;int n,m;cin>>n>>m;for(int i=0;i<n;i++){scanf("%d",&c[i].val);c[i].no=i+1;c[i].ans=0;}for(int i=0;i<m;i++){scanf("%d",&s[i].val);s[i].no=i+1;s[i].times=0;q.push(s[i]);}sort(c,c+n,cmp1);for(int i=0;i<n;i++){if(!q.empty()){while(temp=q.top(),temp.val>c[i].val){q.pop();temp.times++;temp.val=(temp.val+1)/2;q.push(temp);}if(temp.val==c[i].val){ans1++;ans2+=temp.times;c[i].ans=temp.no;s[temp.no-1].times=temp.times;q.pop();}}}sort(c,c+n,cmp2);cout<<ans1<<" "<<ans2<<endl;for(int i=0;i<m;i++)printf("%d ",s[i].times);printf("\n");for(int i=0;i<n;i++)printf("%d ",c[i].ans);printf("\n");return 0;}
C HDU Today
题目大意：
公交车有n(1<=n<=10000)条路线，第i条路线的起点为Si终点为Ei(Si和Ei为长度不超过30的字符串)，问从起始站start到终点站end最少需要多少时间。
一组数据中的地名数不超过150。
多组数据。
解题思路：
用map把地名映射成序号之后就是一道最短路裸题了，最多150个点、10000条边，随便做。。。
时间复杂度o(n*log(150)+n)，空间复杂度o(n)。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007map <string,int> mp;int nums,dis,ss1,ss2;string s1,s2;bool life[166];int q[100005],l,r,dp[166],temp0,temp1,temp2;struct Edge{int to,dis;}temp;vector <Edge> v[166];int main(){q[0]=1;int n;while(cin>>n,n>=0){l=0;r=1;dp[2]=123456789;memset(life,0,sizeof(life));mp.clear();cin>>s1;mp[s1]=1;cin>>s2;if(mp[s2]==1)dp[2]=0;mp[s2]=2;nums=3;v[1].clear();v[2].clear();for(int i=0;i<n;i++){cin>>s1>>s2;scanf("%d",&temp.dis);if(mp[s1]==0){v[nums].clear();dp[nums]=123456789;ss1=nums++;mp[s1]=ss1;}elsess1=mp[s1];if(mp[s2]==0){v[nums].clear();dp[nums]=123456789;ss2=nums++;mp[s2]=ss2;}elsess2=mp[s2];temp.to=ss2;v[ss1].push_back(temp);temp.to=ss1;v[ss2].push_back(temp);}while(l<r){temp0=q[l++];life[temp0]=0;for(int i=0;i<v[temp0].size();i++){temp1=(v[temp0][i]).to;temp2=dp[temp0]+(v[temp0][i]).dis;if(dp[temp1]>temp2){dp[temp1]=temp2;if(life[temp1]==0){life[temp1]=1;q[r++]=temp1;}}}}if(dp[2]==123456789)printf("-1\n");elseprintf("%d\n",dp[2]);}return 0;}
D Music in Car
题目大意：
有n(1<=n<=200000)首歌，第i首歌能提供ai愉悦度(1<=ai<=10000)、长度为ti(2<=ti<=10^4)秒，从某首歌开始连续听不超过k(1<=k<=2*10^9)秒，其中最多可以有w(1<=w<=n)首歌只听一半的时间(向上取整)，问能得到的最大总愉悦度是多少。
解题思路：
如果当我们确定了从哪首歌开始听，听到哪首歌为止，那么最佳策略就是将这些歌中长度最长的至多w首歌时间折半(向上取整)，然后判断总时间是否超过k，时间复杂度o(n^3)。
当起点确定，那么最右边能达到的终点其实也就确定了，因为如果到某首歌的时候已经没有办法听完，那么剩下的歌肯定也没办法听完。于是我们可以维护两个优先队列PQ1和PQ2，PQ1装当前只听半首的歌，PQ2装当前听了一整首的歌，PQ1时间短的歌在前，PQ2时间长的歌在前。对于新的歌曲：(一)如果当前只听半首的歌还没有达到w，那么考虑剩余时间够不够听半首；(二)如果当前已经听了w首歌，考虑这w首歌中时间最长的和当前歌曲谁时间更长，然后考虑最优的分配下能不能听这首歌。当新歌曲不能听的时候，当前起点对应的终点就确定了，用当前愉悦度更新答案就行了。
如果枚举起点，时间复杂度o(n^2*log(n))，还是要炸。于是我们记录当前在听的歌曲中每一首属于哪个优先队列，然后每次更换起点的时候把之前起点的时间和愉悦度都进行复原，如果之前起点那首歌只听了半首，就把听了整首的歌中最长的那一首改成只听半首，维护一下两个PQ，这样时间复杂度就又少了一个n。
小细节：注意处理好某个起点对应无歌可听的情况。
时间复杂度o(n*log(n))，空间复杂度o(n)。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007struct Song{int no,a,t;friend bool operator <(Song x1,Song x2){return x1.t>x2.t;}friend bool operator >(Song x1,Song x2){return x1.t<x2.t;}}s[200005],temp1,temp2;int life[200005];pq <Song,vector<Song>,less<Song> > q1;pq <Song,vector<Song>,greater<Song> > q2;int main(){int n,m,k;int ans=0,now=0,gg=0;cin>>n>>m>>k;int l,r=0;for(int i=1;i<=n;i++)s[i].no=i;for(int i=1;i<=n;i++)scanf("%d",&s[i].a);for(int i=1;i<=n;i++)scanf("%d",&s[i].t);for(l=1;l<=n;l++){if(life[l-1]==1){now-=s[l-1].a;k+=(s[l-1].t+1)/2;if(gg){gg--;while(temp2=q2.top(),life[temp2.no]!=2)q2.pop();q2.pop();q1.push(temp2);life[temp2.no]=1;k+=s[temp2.no].t/2;}elsem++;life[l-1]=0;}if(life[l-1]==2){gg--;now-=s[l-1].a;k+=s[l-1].t;life[l-1]=0;}while(r<n){if(m){if(k>=(s[r+1].t+1)/2){r++;m--;q1.push(s[r]);now+=s[r].a;k-=(s[r].t+1)/2;life[r]=1;}elsebreak;}else{while(temp1=q1.top(),life[temp1.no]!=1)q1.pop();if(temp1.t<s[r+1].t){if(k>=temp1.t/2+(s[r+1].t+1)/2){r++;k-=temp1.t/2+(s[r].t+1)/2;q1.pop();life[temp1.no]=2;gg++;q2.push(temp1);now+=s[r].a;life[r]=1;q1.push(s[r]);}elsebreak;}else{if(k>=s[r+1].t){r++;k-=s[r].t;now+=s[r].a;gg++;life[r]=2;q2.push(s[r]);}elsebreak;}}}r=max(l,r);ans=max(ans,now);}cout<<ans<<endl;return 0;}
E Leaving Auction
题目大意：
有n(1<=n<=200000)个人进行拍卖，给出按时间顺序的n次递增的出价，第i次出价的出价人为ai(1<=ai<=n)、价格为bi(1<=bi<=10^9)。有q(1<=q<=200000)次询问，第i次询问给出ki(1<=ki<=n)个人的编号，问如果这些人没有参与拍卖，那按照拍卖的进程，最终得拍人是谁，他花了多少钱。
sum(k)<=200000。
解题思路：
题意的最后一句是重点。
我们建n个vector储存对应编号的人的历史出价，然后把所有人的最高出价连同出价人从大到小进行排序，然后对于每次询问，我们把所有没参与拍卖的人标记起来，然后从头开始找剩下参与拍卖的人中历史出价最高和第二高的，这个时候得拍人和他的最有力竞争者就已经确定了。接下来去得拍人的历史出价中二分查找比竞争者的最高出价要高的最低出价就是他最终花的钱。因为有k个人没参与竞拍，所以最多找k+2个人就能知道出价最高和第二高的人是谁。
小细节：注意处理好剩下人中没人出过价和剩下人中只有一个人出过价的情况。尤其注意处理所有人都没参与拍卖的情况。尽量用记录每次不参与人的编号，样例末尾再重置的办法，不要用memset来把所有人的状态重置，时间差距很大。
时间复杂度o(q*log(n)+sum(k))，空间复杂度o(n)。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007vector <int> v[200005];queue <int> qu;struct Mans{int no,val;}p[200005];bool cmp(Mans x1,Mans x2){return x1.val>x2.val;}bool life[200005];int ask(int no,int val){int mid,l=0,r=v[no].size()-1;while(l<r){mid=(l+r)/2;if(v[no][mid]>val)r=mid;elsel=mid+1;}return v[no][l];}int main(){int n,q,k;int ans1,gg,now,a,b;cin>>n;for(int i=1;i<=n;i++){p[i].no=i;scanf("%d%d",&a,&b);p[a].val=b;v[a].push_back(b);}p[n+1].val=0;sort(p+1,p+1+n,cmp);cin>>q;while(q--){ans1=0;now=1;scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&gg);life[gg]=1;qu.push(gg);}while(!ans1 || life[p[now].no]){if(!life[p[now].no])ans1=now;now++;}if(!p[ans1].val)printf("0 0\n");elseprintf("%d %d\n",p[ans1].no,ask(p[ans1].no,p[now].val));while(!qu.empty()){life[qu.front()]=0;qu.pop();}}return 0;}
F Pearls in a Row
题目大意：
长度为n(1<=n<=300000)的数列，第i项为ai(1<=ai<=10^9)，将其分为若干段，要求每段中至少有两项相等，问最多能分成多少段。
输出分法。
解题思路：
这题一看就很dp。。。
扫一遍数列，动态维护每个数字上一次出现的位置，考虑当前项如果和该数字上一次出现的位置分在同一段里，答案会不会更优。更新答案的时候顺便记录划分方案。因为数字的范围是10^9，所以要用到map来维护上一次出现的位置。
小细节：注意无法划分的情况。注意数列头尾的处理。
时间复杂度o(n*log(n))，空间复杂度o(n)。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007map <int,int> mp;int dp[300005],pre[300005];int main(){int n,now,temp;cin>>n;for(int i=1;i<=n;i++){scanf("%d",&now);temp=mp[now];pre[i]=pre[i-1];dp[i]=dp[i-1];if(temp && dp[temp-1]+1>dp[i-1]){pre[i]=temp-1;dp[i]=dp[temp-1]+1;}mp[now]=i;}temp=dp[n];if(temp){printf("%d\n",temp);while(temp--){if(temp)printf("%d %d\n",pre[n]+1,n);elseprintf("%d %d\n",1,n);n=pre[n];}}elseprintf("-1\n");return 0;}