首页 > ACM题库 > HDU-杭电 > HDU 3279-Nth Largest Value-分治-[解题报告]HOJ
2014
03-13

HDU 3279-Nth Largest Value-分治-[解题报告]HOJ

Nth Largest Value

问题描述 :

For this problem, you will write a program that prints the Nth largest value in a fixed sized array of integers. To make things simple, N will be 3 and the array will always be have 10 decimal integer values.

输入:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set consists of a single line containing the data set number, followed by a space,followed by 10 space separated decimal integers whose values are between 1 and 1000 inclusive.

输出:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set consists of a single line containing the data set number, followed by a space,followed by 10 space separated decimal integers whose values are between 1 and 1000 inclusive.

样例输入:

4
1 1 2 3 4 5 6 7 8 9 1000
2 338 304 619 95 343 496 489 116 98 127
3 931 240 986 894 826 640 965 833 136 138
4 940 955 364 188 133 254 501 122 768 408

样例输出:

1 8
2 489
3 931
4 768

            思路:建图很容易,排名和人的标号连边,倒着匹配就可以输出最大字典序

            代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define clr(a,b) memset(a,b,sizeof(a))
#define maxn 65
#define maxm 100005

using namespace std;
int next[maxn*maxm],ev[maxn*maxm],first[maxn];
int vis[maxm],mat[maxm],matx[maxn],ca,n,x,y,e;
void add(int u,int v)
{
    next[e]=first[u],ev[e]=v,first[u]=e++;
}
bool find(int u)
{
    int v;
    for(int i=first[u];i!=-1;i=next[i])
    {
        v=ev[i];
        if(!vis[v])
        {
            vis[v]=1;
            if(mat[v]==-1||find(mat[v]))
            {
                mat[v]=u;
                matx[u]=v;
                return 1;
            }
        }
    }
    return 0;
}
int Hungary(int nx)
{
    int Max=0;
    clr(mat,-1);
    clr(matx,-1);
    for(int i=nx;i>=1;i--)
    {
        clr(vis,0);
        if(find(i))
            Max++;
    }
    return Max;
}
int main()
{
    //freopen("D:/d.txt","r",stdin);
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d",&n);
        clr(first,-1);
        e=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d",&x,&y);
            for(int j=x;j<=y;j++)
               add(i,j);
        }
        int ans=Hungary(n);
        printf("%d\n",ans);
        int count=0;
        for(int i=1;i<=n;i++)
          if(matx[i]!=-1)
          {
              count++;
              if(count==ans)
                 printf("%d\n",i);
              else printf("%d ",i);
          }
    }
    return 0;
}

参考:http://blog.csdn.net/a1ways_online/article/details/7775410


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。