SGU 416 Optimal Dartboard(找规律)

雨点打透心脏的1/2处 2022-06-05 00:38 128阅读 0赞

#### 416. Optimal Dartboard ####

Time limit per test: 0.25 second(s)   
Memory limit: 262144 kilobytes

input: standard   
output: standard

A dartboard is a disc divided into  *n* segments, with each segment labeled with a distinct positive integer between 1 and  *n*. That integer indicates the score for hitting the segment. To make the game more interesting, the arrangement of numbers is chosen in such a way that the risk is maximized. The risk is estimated based on the differences in scores of adjacent segments.   
  
We're studying the following 'double-layered' structure of segments in this problem:  
  
![23dee17aaab0974111a45b01b07221d7_v_1510474493][]   
  
I.e.,  *n* is always even, and we split the disc into two layers of  ![ea9318c59f87bb559f0d6cb31796fdbe_v_1510474493][] parts along the circumference. We enumerate the segments in the following manner: the first segment is some outer segment, the second segment is the corresponding inner segment, the third segment is some adjacent outer segment, etc. An example of this enumeration is shown on the picture above.   
  
The total risk is defined as the sum of squared differences between the scores of adjacent segments. If the value assigned to segment  *i* is  *a*  *i*, then the risk is:   
  
*R*=∑  *i*=1  *n*(  *a*  *i*\-  *a*  *i*\+2)  2\+∑  *i*=1  *n*/2(  *a*  2i-1\-  *a*  2i)  2   
  
(we assume  *a*  *n*\+1=a  1 and  *a*  *n*\+2=a  2 in this formula).   
  
You are to place the numbers from 1 through  *n* into the segments in such a way that the total risk  *R* is maximized.

**Input**

The input file contains an even integer number  *n* (6 ≤  *n* ≤ 100).

**Output**

Output  *n* integer numbers:  *a*  1,  *a*  2,...,  *a*  *n*, separated with single spaces. In case there are several possible solutions, output any.

**Example(s)**

<table style="border-collapse:collapse; border:1px solid black"> 
 <tbody> 
  <tr> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">sample input</pre> </td> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">sample output</pre> </td> 
  </tr> 
  <tr> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">10
</pre> </td> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">2 9 7 4 6 5 3 8 10 1
</pre> </td> 
  </tr> 
 </tbody> 
</table>

题意：

给你一个偶数n，表示一个内环有n/2个空，外环也有n/2个空，且内外环的空一一对应的图。如题目中的图所示，它表示n为20的图形。现在你要把1到n这n个数往空里填，使得每两个相邻的空的数的差的平方和最大。然后按照图示顺序输出这n个数。

思路：

很明显，要想使差的平方和最大，最小的那一个周围肯定是最大的三个数，然后第二大的数旁边要放上第二小的数，然后第三大的数旁边要放上第三小的数，依次类推，很容易把这个环形的每个空按要求填满。那么接下来就只需要按要求输出就行了。随便列几个情况，很容易发现规律，当n/2为偶数的时候，我们只需要按大小小大或小大大小的顺序输出即可，当n/2为奇数的时候，除了中间那一组以外其余的仍然是大小小大或小大大小的顺序，而中间那一组只要不变就行了，具体看代码。

AC代码：

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 1005;
    const int MOD = 1e9 + 7;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b){LL res = 1;for (int i = 1; i <= b; i++)res *= a;return res;}
    
    int ans[105];
    
    int main()
    {
    	int i, n, p, q;
    	bool flag1, flag2;
    	while (scanf("%d", &n) != EOF)
    	{
    		flag2 = n % 4 == 0 ? false : true;
    		p = 1;
    		q = n;
    		flag1 = true;
    		i = 0;
    		while (p<n)
    		{
    			if (flag1)
    			{
    				ans[++i] = max(p, q);
    				ans[++i] = min(p, q);
    				p += 2;
    				q -= 2;
    			}
    			else
    			{
    				ans[++i] = min(p, q);
    				ans[++i] = max(p, q);
    				p += 2;
    				q -= 2;
    			}
    			if (flag2 == true && p > q)//跳过中间这一组的异或步骤
    			{
    				flag2 = false;
    				continue;
    			}
    			flag1 ^= 1;
    		}
    		for (int j = 1; j <= i; j++)
    			if (j == 1)
    				printf("%d", ans[j]);
    			else
    				printf(" %d", ans[j]);
    		printf("\n");
    	}
    }

[23dee17aaab0974111a45b01b07221d7_v_1510474493]: https://odzkskevi.qnssl.com/23dee17aaab0974111a45b01b07221d7?v=1510474493
[ea9318c59f87bb559f0d6cb31796fdbe_v_1510474493]: https://odzkskevi.qnssl.com/ea9318c59f87bb559f0d6cb31796fdbe?v=1510474493