[USACO 2010 Jan B]Theater Seating

Here's a diagram of a small (11 x 5) theater where the seat's 'priority' is shown with #1 being the best: Seat Number 1 2 3 4 5 6 7 8 9 10 11 +---------------------------------- Row 5 | 54 50 44 38 32 29 33 39 45 51 55 Row 4 | 52 42 34 25 21 18 22 26 35 43 53 Row 3 | 48 36 23 14 12 9 13 15 24 37 49 Row 2 | 46 30 19 10 5 4 6 11 20 31 47 Row 1 | 40 27 16 7 2 1 3 8 17 28 41 Write a program that prints the seating priority chart for a supplied width and row count.

C(clang 3.9) 解法, 执行用时: 4ms, 内存消耗: 420K, 提交时间: 2019-11-16 23:03:28

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct qian
{
    int num;
    double dis;
}ccc;
int com(const void *a, const void *b)
{
    if(((ccc *)a)->dis == ((ccc *)b)->dis)
        return ((ccc *)a)->num - ((ccc *)b)->num;
    return (((ccc *)a)->dis - ((ccc *)b)->dis)>0?1:-1;
}
int main(void)
{
    int l,r;
    scanf("%d %d",&r,&l);
    int seat[l*r];
    ccc a[l*r];
    for(int i = 0; i <= l-1; i++)
    {
        for(int j = 0; j <= r-1; j++)
        {
            a[i*r+j].num = i*r+j;
            a[i*r+j].dis = sqrt(i*i + abs(r/2 - j)*abs(r/2 - j));
        }
    }
    qsort(a, l*r, sizeof(ccc), com);
    for(int i = 0; i < l*r; i++)
    {
        seat[a[i].num] = i;
    }
    for(int i = l-1; i >= 0; i--)
    {
        for(int j = 0; j <= r-1; j++)
        {
            printf("%d ",seat[i*r+j]+1);
        }
        putchar('\n');
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 536K, 提交时间: 2019-11-16 20:59:30

#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<string>
#include<string.h>
#include<iostream>
#define ll long long
using namespace std;
struct mmp
{
	int x,y;
	double dis;
	bool operator < (const mmp &w) const
	{
		if(dis==w.dis)
		{
			if(x==w.x)
			return y<w.y;
			return x<w.x;
		}
		return dis<w.dis;
	}
}a[6010];
int n,m,tot;
int mp[60][110];
int main()
{
	scanf("%d%d",&m,&n);
	double x=1,y=(m+1)/2;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		a[tot].x=i;
		a[tot].y=j;
		a[tot].dis=(x-i)*(x-i)+(y-j)*(y-j);
		tot++;
	}
	sort(a,a+tot);
	for(int i=0;i<tot;i++)
	mp[a[i].x][a[i].y]=i+1;
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=m;j++)
		printf("%d ",mp[i][j]);
		printf("\n");
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 464K, 提交时间: 2019-11-18 00:21:43

#include <bits/stdc++.h>
using namespace std;
#define inc(i,n) for (int i=0;i<n;i++)
typedef long long ll;

struct Node{
	int x,y,d;
	bool operator<(const Node &v)const{
		if (d==v.d) return x==v.x?y<v.y:x>v.x;
		return d<v.d;
	}
}w[10010];
int ans[110][110],wc;

int main(){
	int n,m; cin>>m>>n;
	inc(i,n) inc(j,m)
		w[wc++]={i,j,(n-1-i)*(n-1-i)+(j-m/2)*(j-m/2)};
	sort(w,w+wc);
	inc(i,wc) ans[w[i].x][w[i].y]=i+1;
	for (int i=0;i<n;i++,puts(""))
		inc(j,m) printf("%d ",ans[i][j]);
	return 0;
}

详情