[关闭]
@iamtts 2017-01-26T19:44:25.000000Z 字数 4766 阅读 969

寒假第三次训练-花式STL

A - Moo University - Financial Aid

题目大意：给定c组数据，形式为：分数+资金，要求选出n（n为奇数）组，保证不仅资金总和小于f，而且分数中位数最大。

解题思路：先排序数据，分数由高到低选定一组数据，数据前方后方都有（n-1）/2组数据，建立low[i]表示中位数为第i组数据的分数时，前方最小资金和，up[i]同理。low[i]和up[i]用priority_queue计算，保证队列内部有不超过(n-1)/2的元素，一旦溢出就pop最大的元素。

AC代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <string>
  4. #include <iostream>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <stack>
  8. #include <vector>
  9. #include <queue>
  10. #define MAXC 100010
  11. using namespace std;
  13. pair<int,int> cow[MAXC];
  14. long long low[MAXC],up[MAXC];
  16. int main()
  17. {
  18.     int N,C,i,m,f=0;
  19.     long long F,sum=0;
  20.     scanf("%d%d%I64d",&N,&C,&F);
  21.     for (i=0; i<C; i++)
  22.         scanf("%d%d",&cow[i].first,&cow[i].second);
  23.     sort(cow,cow+C);
  24.     m=(N-1)/2;
  25.     priority_queue<int> q1,q2;
  26.     for (i=0; i<C; i++)
  27.     {
  28.         int flag=0;
  29.         if (q1.size()==m)
  30.         {
  31.             flag=1;
  32.             low[i]=sum;
  33.             q1.push(cow[i].second);
  34.             sum+=cow[i].second;
  35.             sum-=q1.top();
  36.             q1.pop();
  37.         }
  38.         if (flag==0)
  39.         {
  40.             q1.push(cow[i].second);
  41.             sum+=cow[i].second;
  42.         }
  43.     }
  44.     sum=0;
  45.     for (i=C-1; i>=0; i--)
  46.     {
  47.         int flag=0;
  48.         if (q2.size()==m)
  49.         {
  50.             flag=1;
  51.             up[i]=sum;
  52.             q2.push(cow[i].second);
  53.             sum+=cow[i].second;
  54.             sum-=q2.top();
  55.             q2.pop();
  56.         }
  57.         if (flag==0)
  58.         {
  59.             q2.push(cow[i].second);
  60.             sum+=cow[i].second;
  61.         }
  62.     }
  63.     for (i=C-m-1; i>=m; i--)
  64.     {
  65.         //printf("low:%d up:%d\n",low[i],up[i]);
  66.         if (low[i]+cow[i].second+up[i]<=F)
  67.         {
  68.             f=1;
  69.             printf("%d\n",cow[i].first);
  70.             break;
  71.         }
  72.     }
  73.     if(f==0) printf("-1\n");
  74.     return 0;
  75. }

B - Sockets

题目大意：有n台电脑，m个插座，电脑和插座都有自己的power，必须满足power相等才能将电脑连接插座，现在提供无限个适配器，可以将插座的power变为（power+1）/2，一个插座上可以加无限个适配器，求最大的电脑连接量同时满足适配器使用最少，输出每一台电脑对应的插座和每一个插座插入的适配器。

解题思路：将插座的power排序，电脑放入map，以power为关键字排序，一边给插座加适配器，一边在map里查找power刚好相等的电脑，因为同一台电脑要使适配器最少的话肯定是从power本来就小的插座开始加适配器，值得注意的是电脑的power可能重复，map是不允许重复的，我们利用vector来解决。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. using namespace std;
  9. struct Soc
  10. {
  11.     long long x;
  12.     int pos;
  13. };
  14. #define MAX 200005
  15. map<long long,int> pc;
  16. struct Soc soc[MAX];
  17. int pc_soc[MAX]={0};
  18. long long adp[MAX]={0};
  19. vector<int> pc_mul[MAX];
  21. bool compare(Soc a,Soc b)
  22. {
  23.     return a.x<b.x;
  24. }
  25. int main()
  26. {
  27.     int n,m,i,c=0,count_=0;
  28.     long long a,b,u=0,u1=0,temp;
  30.     scanf("%d%d",&n,&m);
  31.     for (i=1;i<=n;i++)
  32.     {
  33.         int x;
  34.         scanf("%I64d",&a);
  35.         x=pc[a];
  36.         if (x==0)
  37.         {
  38.             pc[a]=++count_;
  39.             pc_mul[count_].push_back(i);
  40.         }
  41.         else
  42.         {
  43.             pc_mul[x].push_back(i);
  44.         }
  45.     }
  46.     for (i=1;i<=m;i++)
  47.     {
  48.         scanf("%I64d",&soc[i].x);
  49.         soc[i].pos=i;
  50.     }
  51.     sort(soc+1,soc+m+1,compare);
  53.     for (i=1;i<=m;i++)
  54.     {
  55.         int flag=0;
  56.         u1=0;
  57.         temp=soc[i].x;
  58.         map<long long,int>::iterator iter;
  59.         while (temp)
  60.         {
  61.             if((iter=pc.find(temp)) != pc.end())
  62.             {
  63.                 if (pc_mul[iter->second].size()>0)
  64.                 {
  65.                     flag=1;
  66.                     int p=pc_mul[iter->second].size();
  67.                     c++;
  68.                     pc_soc[pc_mul[iter->second][p-1]]=soc[i].pos;
  69.                     pc_mul[iter->second].pop_back();
  70.                     break;
  71.                 }
  72.             }
  73.             if (temp==1) break;
  74.             else
  75.             {
  76.                 temp=(temp+1)/2;
  77.                 u1++;
  78.             }
  79.         }
  80.         if (flag==0) u1=0;
  81.         u+=u1;
  82.         adp[soc[i].pos]+=u1;
  83.     }
  85.     printf("%d %I64d\n",c,u);
  86.     for(i=1;i<=m;i++)
  87.         printf("%I64d%c",adp[i],i==m?'\n':' ');
  88.     for(i=1;i<=n;i++)
  89.         printf("%d%c",pc_soc[i],i==n?'\n':' ');
  90. }

C - HDU Today

题目大意：给定n组形式为：地点a，地点b，时间（a，b为字符串），并且知道起止地点，求最短时间

解题思路：将字符串转换为数字下标，用最短路算

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. using namespace std;
  9. struct Soc
  10. {
  11.     long long x;
  12.     int pos;
  13. };
  14. #define MAX 200005
  15. map<long long,int> pc;
  16. struct Soc soc[MAX];
  17. int pc_soc[MAX]={0};
  18. long long adp[MAX]={0};
  19. vector<int> pc_mul[MAX];
  21. bool compare(Soc a,Soc b)
  22. {
  23.     return a.x<b.x;
  24. }
  25. int main()
  26. {
  27.     int n,m,i,c=0,count_=0;
  28.     long long a,b,u=0,u1=0,temp;
  30.     scanf("%d%d",&n,&m);
  31.     for (i=1;i<=n;i++)
  32.     {
  33.         int x;
  34.         scanf("%I64d",&a);
  35.         x=pc[a];
  36.         if (x==0)
  37.         {
  38.             pc[a]=++count_;
  39.             pc_mul[count_].push_back(i);
  40.         }
  41.         else
  42.         {
  43.             pc_mul[x].push_back(i);
  44.         }
  45.     }
  46.     for (i=1;i<=m;i++)
  47.     {
  48.         scanf("%I64d",&soc[i].x);
  49.         soc[i].pos=i;
  50.     }
  51.     sort(soc+1,soc+m+1,compare);
  53.     for (i=1;i<=m;i++)
  54.     {
  55.         int flag=0;
  56.         u1=0;
  57.         temp=soc[i].x;
  58.         map<long long,int>::iterator iter;
  59.         while (temp)
  60.         {
  61.             if((iter=pc.find(temp)) != pc.end())
  62.             {
  63.                 if (pc_mul[iter->second].size()>0)
  64.                 {
  65.                     flag=1;
  66.                     int p=pc_mul[iter->second].size();
  67.                     c++;
  68.                     pc_soc[pc_mul[iter->second][p-1]]=soc[i].pos;
  69.                     pc_mul[iter->second].pop_back();
  70.                     break;
  71.                 }
  72.             }
  73.             if (temp==1) break;
  74.             else
  75.             {
  76.                 temp=(temp+1)/2;
  77.                 u1++;
  78.             }
  79.         }
  80.         if (flag==0) u1=0;
  81.         u+=u1;
  82.         adp[soc[i].pos]+=u1;
  83.     }
  85.     printf("%d %I64d\n",c,u);
  86.     for(i=1;i<=m;i++)
  87.         printf("%I64d%c",adp[i],i==m?'\n':' ');
  88.     for(i=1;i<=n;i++)
  89.         printf("%d%c",pc_soc[i],i==n?'\n':' ');
  90. }

F - Pearls in a Row

题目大意：给定n个数字，要求用隔板法在数字间进行划分，划分出的每一组必须包含至少两个一样的数字，求插入隔板最多的方案的每一组首尾的下标，若不存在输出-1

解题思路：从前往后读一个数据向map存一个数据，并判断是否已经存在相同数字，有则记录并且销毁map，这样贪心的读到两个相同数就记录。值得注意的是相同数的第一个数记录的应该是一段数据最左端的下标，第二个数记录的是本身的下标，但是如果作为最后一段数据，相同数的第二个数却不是输入数据的最后一个就需要把记录的值改为最后数的下标。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. using namespace std;
  9. #define MAXN 300005
  11. typedef struct Seg
  12. {
  13.     long long left;
  14.     long long right;
  15. } seg;
  17. long long pearl[MAXN];
  18. vector<seg> rec;
  19. map<long long,int> p;
  21. int main()
  22. {
  23.     long long n,count_=0,k=1;
  24.     scanf("%I64d",&n);
  25.     for (long long i=1; i<=n; i++)
  26.     {
  27.         scanf("%I64d",&pearl[i]);
  28.         long long x;
  29.         x=p[pearl[i]];
  30.         if (x==0)
  31.             p[pearl[i]]=k;
  32.         else
  33.         {
  34.             seg temp;
  35.             temp.left=p[pearl[i]];
  36.             temp.right=i;
  37.             k=i+1;
  38.             rec.push_back(temp);
  39.             p.clear();
  40.             count_++;
  41.         }
  42.     }
  43.     if (count_!=0 && rec.back().right!=n) rec.back().right=n;
  44.     if (count_==0) printf("-1\n");
  45.     else
  46.     {
  47.         printf("%I64d\n",count_);
  48.         for (long long i=0; i<rec.size(); i++)
  49.             printf("%I64d %I64d\n",rec[i].left,rec[i].right);
  50.     }
  51. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注