[关闭]
@lawk97 2017-04-19T16:24:02.000000Z 字数 4688 阅读 1028

寒假专题训练--花式STL

VJ地址

STL

A - Moo University - Financial Aid

POJ - 2010
- 题意
奶牛大学招生啦。有C只奶牛申请，会录取N只（N为奇数）。每只奶牛上学需要不同数额的赞助，而学校可以用于赞助奶牛学生的总经费为F。在学校经费的限制下，要使录取的N只奶牛TA们的成绩中位数尽可能高，求出这中位数的可能最大值。
- 思路
首先将奶牛按成绩高低排序。
因为要录取N只奶牛，所以成绩是中位数的奶牛在所有奶牛中的次序必然在[N/2+1,C-N/2]之间取值。在TA前面的奶牛和在TA后面的奶牛，各录取需赞助少的N/2只。如果TA所需的赞助加上其他奶牛需要的赞助之和，小于等于总经费F,则说明这只奶牛的成绩可以作为中位数。
在可作为“中间奶牛”的奶牛中，取成绩的最高的那个。
使用优先队列，便于找到当前奶牛前面和后面的，需赞助少的N/2只。

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <cstring>
  6. #include <string>
  7. #include <queue>
  8. using namespace std;
  10. int n,c,f;
  11. int ans=-1;
  12. int lef[100005],rig[100005];
  13. struct student
  14. {
  15.     int score,cost;
  16. }cow[100005];
  17. priority_queue<int>q1,q2;
  19. int cmp(student a,student b)
  20. {
  21.     return a.score<b.score;
  22. }
  24. int main()
  25. {
  26.     scanf("%d%d%d",&n,&c,&f);
  27.     for(int i=0;i<c;i++)
  28.         scanf("%d%d",&cow[i].score,&cow[i].cost);
  29.     sort(cow, cow+c, cmp);
  30.     int l=n/2,r=c-n/2-1;
  31.     int sum1=0,sum2=0;
  32.     for(int i=0;i<l;i++)
  33.     {
  34.         sum1+=cow[i].cost;
  35.         q1.push(cow[i].cost);
  36.     }
  37.     for(int i=l;i<=r;i++)
  38.     {
  39.         lef[i]=sum1;
  40.         q1.push(cow[i].cost);
  41.         int top=q1.top();
  42.         sum1+=cow[i].cost-top;
  43.         q1.pop();
  44.     }
  45.     for(int i=c-1;i>r;i--)
  46.     {
  47.         sum2+=cow[i].cost;
  48.         q2.push(cow[i].cost);
  49.     }
  50.     for(int i=r;i>=l;i--)
  51.     {
  52.         rig[i]=sum2;
  53.         q2.push(cow[i].cost);
  54.         int top=q2.top();
  55.         sum2+=cow[i].cost-top;
  56.         q2.pop();
  57.     }
  58.     for(int i=r;i>=l;i--)
  59.     {
  60.         if(cow[i].cost+lef[i]+rig[i]<=f)
  61.         {
  62.             ans=cow[i].score;
  63.             break;
  64.         }
  65.     }
  66.     printf("%d\n",ans);
  67.     return 0;
  68. }

B - Sockets

CodeForces - 732E
- 题意
有n台电脑，m个插座，若电脑与插座电压相同，则可以将其连接并正常使用该电脑。也可将插座与适配器相连，转化为一个电压为原值一半（向上取整）的新插座。已知适配器数量充足。
求最多有多少台电脑可用，若有多种方案，以适配器使用量最少的一种为优。
- 思路
电源的电压只能降低，不能升高。
若一个电源的电压，既可以适配一个需电压大的电脑，又可以适配一个需电压小的电脑，那么使他适配需电压大的电脑，既可以保证尽可能多的电脑被供能（贪心），又可以减少适配器的使用。
所需电压比各种电源的供电压最大值还大的电脑，一定不能使用。
所供电压比各种电脑的需电压最大值还大的电源，如果不用适配器，肯定不可以接任何电脑。
因此，可将电源和电脑分别按电压从大到小排序，进行比对。因为电源电压可以变化，且我们需要尽可能控制适配器的使用，所以使用优先队列来放置电源。放置电源的优先队列中，电压高的优先，电压相等的电源所用适配器少的优先。
具体思路如下程序。
- 代码

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <map>
  7. #include <stack>
  8. #include <queue>
  9. using namespace std;
  11. int n,m,use=0,sum=0;
  13. struct sw{
  14.     int id,vol,num;
  15.     friend bool operator <(sw a ,sw b){//优先队列默认队头元素最大
  16.         if(a.vol!=b.vol)
  17.             return a.vol<b.vol;
  18.         return a.num>b.num;
  19.     }
  20. }s[200005];
  22. struct cu{
  23.     int id,vol,ans;
  24. }c[200005];
  26. priority_queue<sw> pq;
  28. int cmp_id(cu a,cu b){
  29.     return a.id<b.id;
  30. }
  32. int cmp_v(cu a ,cu b){
  33.     return a.vol>b.vol;
  34. }
  36. int main(){
  38.     scanf("%d%d",&n,&m);
  39.     for(int i=0;i<n;i++){
  40.         scanf("%d",&c[i].vol);
  41.         c[i].id=i+1;
  42.         c[i].ans=0;
  43.     }
  44.     for(int i=0;i<m;i++){
  45.         sw si;
  46.         scanf("%d",&s[i].vol);
  47.         s[i].id=i+1;
  48.         s[i].num=0;
  49.         pq.push(s[i]);
  50.     }
  53.     sort(c,c+n,cmp_v);
  54.     for(int i=0;i<n;i++){
  55.         if (pq.empty())
  56.         {
  57.             break;
  58.         }
  59.         sw f=pq.top();
  60.         if(f.vol==c[i].vol){
  61.             pq.pop();
  62.             c[i].ans=f.id;
  63.             s[f.id-1]=f;
  64.             sum+=f.num;
  65.             use++;
  66.         }else if(f.vol>c[i].vol){
  67.             pq.pop();
  68.             f.num++;
  69.             f.vol=ceil(1.0*f.vol/2);
  70.             pq.push(f);
  71.             i--;
  72.         }
  73.     }
  74.     sort(c,c+n,cmp_id);
  76.     printf("%d %d\n",use,sum );
  77.     for(int i=0;i<m;i++){
  78.         if (i!=0)
  79.         {
  80.             printf(" ");
  81.         }
  82.         printf("%d",s[i].num );
  83.     }
  84.     printf("\n");
  85.     for(int i=0;i<n;i++){
  86.         if (i!=0)
  87.         {
  88.             printf(" ");
  89.         }
  90.         printf("%d",c[i].ans );
  91.     }
  92.     printf("\n");
  93.     return 0;
  94. }

C - HDU Today

HDU - 2112

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <string>
  7. #include <map>
  8. #include <stack>
  9. #include <queue>
  10. using namespace std;
  12. #define INF 1000005
  14. int n,dir,num,minx,now,ans;
  15. int used[155],sl[155],gra[155][155];
  16. string be,st;
  17. map<string,int> m;
  20. int main(){
  21.     while(~scanf("%d",&n)&&n!=-1){
  22.         cin>>be>>st;
  23.         num=1;
  24.         minx=INF;
  25.         ans=INF;
  26.         m.clear();
  27.         memset(sl,0,sizeof(sl));
  28.         memset(used,0,sizeof(used));
  29.         for (int i = 0; i < 155; ++i)
  30.         {
  31.             for (int j = 0; j < 155; ++j)
  32.             {
  33.                 gra[i][j]=INF;
  34.                 if (i==j)
  35.                 {
  36.                     gra[i][j]=0;
  37.                 }
  38.             }
  39.         }
  41.         m[be]=num++;
  42.         m[st]=num++;
  43.         if (be==st)
  44.         {
  45.             ans=0;
  46.             /*
  47.             must do it to stop the program,
  48.             because there are a wrong m[be]=2
  49.             */
  50.         }
  51.         for(int i=0;i<n;i++){
  52.             cin>>be>>st;
  53.             scanf("%d",&dir);//opertion 'cin' spend too much time
  54.             if(m[be]==0){
  55.                 m[be]=num++;
  56.             }
  57.             if(m[st]==0){
  58.                 m[st]=num++;
  59.             }
  60.             gra[m[be]][m[st]]=dir;
  61.             gra[m[st]][m[be]]=dir;//no direction
  62.         }
  64.         if (ans==0)
  65.         {
  66.             printf("%d\n",ans );
  67.             continue;
  68.         }
  69.         for(int i=1;i<num;i++){
  70.             sl[i]=gra[1][i];
  71.         }
  72.         used[1]=1;
  73.         now=1;
  74.         //now must have initial value,if the begin point can't connect to others,
  75.         for (int i = 2; i < num; ++i)
  76.         {
  77.             minx=INF;
  78.             for(int j=1;j<num;j++){
  79.                 if (!used[j]&&sl[j]<minx)
  80.                 {
  81.                     now=j;
  82.                     minx=sl[j];
  83.                 }
  84.             }
  85.             used[now]=1;
  86.             for (int j = 1; j < num; ++j)
  87.             {
  88.                 if (!used[j]&&sl[now]+gra[now][j]<sl[j])
  89.                 {
  90.                     sl[j]=sl[now]+gra[now][j];
  91.                 }
  92.             }
  93.         }
  94.         if (sl[2]<INF)
  95.         {
  96.             printf("%d\n",sl[2] );
  97.         }else{
  98.             printf("-1\n");
  99.         }
  101.     }
  102.     return 0;
  103. }

F - Pearls in a Row

CodeForces - 620C

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <map>
  7. using namespace std;
  9. int n,l,r,num,flag;
  10. int anl[300005],anr[300005];
  11. map<int,int> p;
  12. int main(){
  13.     scanf("%d",&n);
  14.     l=1;
  15.     r=2;
  16.     num=0;
  17.     flag=0;
  19.     for(int i=1;i<=n;i++){
  20.         int now;
  21.         scanf("%d",&now);
  22.         if (!flag&&p[now]>0) {
  23.             r=i;
  24.             flag=1;
  25.         }
  26.         if(flag&&p[now]>r){
  27.             anl[num]=l;
  28.             anr[num]=r;
  29.             num++;
  30.             l=r+1;
  31.             r=i;
  32.         }
  34.         if (i==n) {
  35.             anl[num]=l;
  36.             anr[num]=n;
  37.             num++;
  38.         }
  39.         p[now]=i;
  40.     }
  41.     if (flag) {
  42.         printf("%d\n",num);
  43.         for (int i=0; i<num; i++) {
  44.             printf("%d %d\n",anl[i],anr[i]);
  45.         }
  46.     }else{
  47.         printf("-1\n");
  48.     }
  49. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注