CF334A Candy Bags 题解

Ggsddu_zzy · 2022-11-12 08:59:09 · 题解

题目传送门

题目大意：

给你 n^2 颗糖，分给 n 人，使每个人的权值相等（第 i 块的权值为 i ），输出第 i 个人选的糖果集合，注意题目中说 n 为偶数。

解题思路：

根据 1+2+\ldots+n-1+n= \dfrac{n}{2}(n+1) 的规律，总结出每组的权值的和其实都是 n^2+1。

从 \ 1 和 n^2 之间找出每一组相加为 n^2+1 的组合，这两个数是相对应的，如当 n\ =4 时，这 n 个人的权值可为 \ 1 和 \ 16，\ 2 和 \ 15，\ 3 和 \ 14 等；再把每一种组合都输出出来即可。

如何找出每一种组合？

把 n^2 分为两节，分别是从 1 到 \dfrac{n^2}{2}，和从 n^2 到 \dfrac{n^2}{2}，当第一节中的数字 i 与第二节中的数字 j 是一组时，i+j==n^2+1；

所以只需要判断 i+j 是否与 n^2+1 相等。

当然，也可以直接从 1 到 \frac{n^2}{2} 找，先把每一个数都输出，再输出 n^2-i+1（ \ 1 也可以加在 i 上）。

为什么要加 \ 1 呢？

因为第一组为 \ 1 和 n^2，而不是 \ 0 和 n^2。

代码1：

#include<iostream> 
using namespace std;
int n,b,c; 
int main()
{ 
   cin>>n;
   b=n*n; 
   c=b/2;
   for(int i=1;i<=c;i++) {              //第一节查找 
        for(int j=b;j>=c;j--){           //第二节查找
            if(i+j==b+1)               //判断是否为一组
                cout<<i<<' '<<j<<"\n";
        }    
   }
   return 0; 
}

代码2：

#include<iostream> 
using namespace std;
int n,b,c; 
int main()
{ 
   cin>>n;
   b=n*n; 
   c=b/2; 
   for(int i=1;i<=c;i++) {                
       cout<<i<<' '<<b-i+1<<"\n";         
   }
   return 0; 
}