toj_2862.cpp

Tianjin University Online Judge 的80多道题目 .

/**2862.   CityStar Time Limit: 2.0 Seconds   Memory Limit: 65536K
Total Runs: 270   Accepted Runs: 141


On planet Citystar the cities look somewhat like stars. There's a small round city center from which straight line streets come out. People in one street feel related and between different streets there's some sportive rivalry. They have programming contests in which each street participates with one team. The organizers want to suggest good team members to the streets and to be unbiased, they ask an alien (you) to help them.

Problem
Each street has houses only on one side of the street (numbered 1, 2, 3, ... starting at the city center), each house has the same size and in each house there's at most one programmer (they just can't live together). For each street you'll get the house numbers of its programmers. Now the idea is that a team is better the more often it practices, and that the closer the members live to each other, the more often they meet to practice. To be precise, we'll want to have the smallest range of houses that covers five programmers (three regular members, one substitute, one coach). For example if you choose house numbers 65, 71, 64, 61 and 81 then their range is 21 houses (81-61+1). If there are several possible teams with the same smallest size range, pick the one that lives closest to the city center (where the contest takes place), i. e. with the smaller house numbers.

Input
The first line contains the number of scenarios. Each scenario describes one street and is given on a single line. The first number tells you the number of programmers in the street (from 5 to 100 000), then follows one house number for each programmer (from 1 to 10 000 000).
Output
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print one line describing the chosen team members in the format shown below. First print the range, then the house numbers in sorted order (with a space before each number). Terminate each scenario with a blank line.
Sample Input

20
10 65 2 71 123 7 45 64 4 61 81
16 111 103 117 105 102 113 119 107 11 3 17 5 2 13 19 7

Sample Output

Scenario #1:
21: 61 64 65 71 81

Scenario #2:
10: 2 3 5 7 11



Source: TUD Programming Contest 2006 Single*/
#include<cstdio>
#include<cstdlib>

int cmpInt( const void *a , const void *b )
{
  int * arg1 = ( int* ) a;
  int *arg2 = ( int* ) b;
  if ( *arg1 > *arg2  )
    return 1;
  else if ( *arg1 == *arg2 )
    return 0;
  else
    return -1;
}
    
int main()
{
  int programmer[ 100010 ];
  int i , j , k , nOfCase , nOfP , min , position , currentD;
  scanf( "%d" , &nOfCase );
  for ( i = 0; i < nOfCase; i++ )
    {
      scanf( "%d" , &nOfP );
      for ( j = 0; j < nOfP; j++ )
	scanf( "%d" , &programmer[ j ] );
      qsort( programmer , nOfP , sizeof( int ) , cmpInt );
      min = programmer[ 4 ] - programmer[ 0 ];
      position = 0;
      for ( j = 1; j < nOfP - 4; j++ )
	{
	  currentD = programmer[ j + 4 ] - programmer[ j ];
	  if ( currentD < min )
	    {
	      min = currentD;
	      position = j;
	    }
	}
      printf( "Scenario #%d:\n" , i + 1 );
      printf( "%d:" , min + 1 );
      for ( j = position; j <= position + 4; j++ )
	{
	  printf( " %d" , programmer[ j ] );
	}
      printf( "\n\n" );
    }
  return 0;
}