首页 > 代码库 > hdu3687 National Day Parade 枚举贪心

hdu3687 National Day Parade 枚举贪心

2024-07-30 13:47:28   224人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=3687

National Day Parade

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1828    Accepted Submission(s): 787


Problem Description
There are n×n students preparing for the National Day parade on the playground. The playground can be considered as a n×m grid. The coordinate of the west north corner is (1,1) , and the coordinate of the east south corner is (n,m).

When training, every students must stand on a line intersection and all students must form a n×n square. The figure above shows a 3×8 playground with 9 students training on it. The thick black dots stand for the students. You can see that 9 students form a 3×3 square.

After training, the students will get a time to relax and move away as they like. To make it easy for their masters to control the training, the students are only allowed to move in the east-west direction. When the next training begins, the master would gather them to form a n×n square again, and the position of the square doesn’t matter. Of course, no student is allowed to stand outside the playground.

You are given the coordinates of each student when they are having a rest. Your task is to figure out the minimum sum of distance that all students should move to form a n×n square.
 

Input
There are at most 100 test cases. 
For each test case: 
The first line of one test case contain two integers n,m. (n<=56,m<=200)
Then there are n×n lines. Each line contains two integers, 1<=Xi<=n,1<= Yi<=m indicating that the coordinate of the ith student is (Xi , Yi ). It is possible for more than one student to stand at the same grid point.

The input is ended with 0 0.
 

Output
You should output one line for each test case. The line contains one integer indicating the minimum sum of distance that all students should move to form a n×n square.
 

Sample Input
2 168
2 101
1 127
1 105
2 90
0 0
 

Sample Output
41
 

Source
2010 Asia Hangzhou Regional Contest


题意：给出N*M的矩阵和N*N个点,所有点只能左右移动,问将所有点排列成矩形的最小步数。

开始题看错了，最后才看见只能左右移，那就很简单了，按x,y排序，枚举矩阵的左上点,每次取的n个肯定只计算y坐标差。。。。

/**
 * @author neko01
 */
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define clr(a) memset(a,0,sizeof a)
#define clr1(a) memset(a,-1,sizeof a)
#define dbg(a) printf("%d\n",a)
typedef pair<int,int> pp;
const double eps=1e-9;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
const LL inf=(((LL)1)<<61)+5;
struct point{
    int x,y;
}a[60*60];
int n,m;
bool cmp(point u,point v)
{
    if(u.x==v.x) return u.y<v.y;
    return u.x<v.x;
}
int gao(int x)
{
    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            ans+=abs(a[i*n+j].y-(x+j));
    return ans;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        for(int i=0;i<n*n;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        sort(a,a+n*n,cmp);
        int ans=INF;
        for(int i=1;i<=m-n+1;i++)
            ans=min(ans,gao(i));
        printf("%d\n",ans);
    }
    return 0;
}



hdu3687 National Day Parade 枚举贪心


联系
我们