`
444878909
  • 浏览: 631592 次
文章分类
社区版块
存档分类
最新评论

HDU 3687 National Day Parade

 
阅读更多

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


题意:

给你一个n*m的方阵,里面有n*n个人并给出坐标,问你最少走多少步可以形成一个n*n的正方形方阵,每个人只能向左向右移动。

题解:

数据量不大,直接暴力搞定,n*n*m


AC代码:

Accepted 3687 46MS 384K 1535 B G++ XH_Reventon
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s)  scanf("%s",s)
#define pi1(a)    printf("%d\n",a)
#define pi2(a,b)  printf("%d %d\n",a,b)
#define mset(a,b)   memset(a,b,sizeof(a))
#define forb(i,a,b)   for(int i=a;i<b;i++)
#define ford(i,a,b)   for(int i=a;i<=b;i++)

typedef long long LL;
const int N=33;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;


int dat[57][201],cnt[57];
int n,m;

int main()
{
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m),n||m)
    {
        int tol=n*n,i,j,x,y,k;
        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=tol;i++)
        {
            scanf("%d%d",&x,&y);
            dat[x][cnt[x]++]=y;
        }
        for(i=1;i<=n;i++)
            sort(dat[i],dat[i]+n);
        int ans=100000000;
        for(i=1;i<=m;i++)
        {
            int sum=0;
            for(j=1;j<=n;j++)
                for(k=0;k<n;k++)
                    sum+=abs(dat[j][k]-i-k);
            if(ans>sum)
                ans=sum;
        }
        printf("%d\n",ans);
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics