P7962-[NOIP2021]方差

题目链接

方差:衡量一组数据的波动程度大小

直接根据方差的定义打出代码，可以骗拿到32pts的好成绩

#include
#include
#include
#include
#include
#include
using namespace std;
int a[10010],n;
double x,ans;
double calc(){
	double sum = 0;
	for(int i=1;i<=n;i++){
		sum += 1.0*(a[i]-x)*(a[i]-x);
	}
	return sum;
}
int main(){
	//freopen("variance.in","r",stdin);
	//freopen("variance.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		x += a[i];
	}
	x /= 1.0*n;
	ans = calc();
	
	//cout<
		no_ok = 0;
		for(int i=n-1;i>=2;i--){
			if(abs((a[i-1]+a[i+1]-a[i])-x)
			//减小数据波动程度
				x += ((a[i-1]+a[i+1]-a[i])-a[i])*1.0/n;
				a[i] = (a[i-1]+a[i+1]-a[i]);
				ans = calc();
				
				//cout<
				//	cout< 
好，扯远了，现在进入正题
 
一、式子 
看到题目的式子：
 D = 
    
     
      
       
        
         1
        
        
         n
        
       
       
        
         ∑
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
       
        (
       
       
        
         a
        
        
         i
        
       
       
        −
       
       
        
         a
        
        
         ˉ
        
       
       
        
         )
        
        
         2
        
       
      
      
       frac {1}{n} sum_{i=1}^{n} (a_{i}-bar {a})^{2}
      
     
    n1​∑i=1n​(ai​−aˉ)2,其中
    
     
      
       
        
         a
        
        
         ˉ
        
       
       
        =
       
       
        
         1
        
        
         n
        
       
       
        
         ∑
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
       
        
         a
        
        
         i
        
       
      
      
       bar a = frac{1}{n} sum_{i = 1}^{n} a_i
      
     
    aˉ=n1​∑i=1n​ai​
 要求输出方差的最小值的平方，即
    
     
      
       
        
         D
        
        
         2
        
       
      
      
       D^{2}
      
     
    D2
 设最终答案为ans,我们得到这样一条式子：
 
     
      
       
        
         a
        
        
         n
        
        
         s
        
        
         =
        
        
         
          n
         
         
          2
         
        
        
         ⋅
        
        
         
          1
         
         
          n
         
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         (
        
        
         
          a
         
         
          i
         
        
        
         −
        
        
         
          a
         
         
          ˉ
         
        
        
         
          )
         
         
          2
         
        
       
       
        ans = n^2 cdot frac {1}{n} sum_{i=1}^{n} (a_{i}-bar {a})^{2}
       
      
     ans=n2⋅n1​i=1∑n​(ai​−aˉ)2
 化简一下：
 
     
      
       
        
         a
        
        
         n
        
        
         s
        
        
         =
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         (
        
        
         
          a
         
         
          i
         
        
        
         −
        
        
         
          a
         
         
          ˉ
         
        
        
         
          )
         
         
          2
         
        
       
       
        ans = n sum_{i=1}^{n} (a_{i}-bar {a})^{2}
       
      
     ans=ni=1∑n​(ai​−aˉ)2
 

     
      
       
        
         a
        
        
         n
        
        
         s
        
        
         =
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
         
          2
         
        
        
         −
        
        
         2
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
        
        
         
          a
         
         
          ˉ
         
        
        
         +
        
        
         
          n
         
         
          2
         
        
        
         
          
           a
          
          
           ˉ
          
         
         
          2
         
        
       
       
        ans = n sum_{i=1}^{n} a_{i}^2-2nsum_{i=1}^{n} a_{i} bar {a} + n^2bar a^2 
       
      
     ans=ni=1∑n​ai2​−2ni=1∑n​ai​aˉ+n2aˉ2
 

     
      
       
        
         a
        
        
         n
        
        
         s
        
        
         =
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
         
          2
         
        
        
         −
        
        
         2
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
        
        
         
          a
         
         
          ˉ
         
        
        
         +
        
        
         n
        
        
         ⋅
        
        
         n
        
        
         
          a
         
         
          ˉ
         
        
        
         ⋅
        
        
         
          a
         
         
          ˉ
         
        
       
       
        ans = n sum_{i=1}^{n} a_{i}^2-2nsum_{i=1}^{n} a_{i} bar {a} + ncdot nbar acdot bar a 
       
      
     ans=ni=1∑n​ai2​−2ni=1∑n​ai​aˉ+n⋅naˉ⋅aˉ
 

     
      
       
        
         a
        
        
         n
        
        
         s
        
        
         =
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
         
          2
         
        
        
         −
        
        
         2
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
        
        
         
          a
         
         
          ˉ
         
        
        
         +
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
        
        
         
          a
         
         
          ˉ
         
        
       
       
        ans = n sum_{i=1}^{n} a_{i}^2-2nsum_{i=1}^{n} a_{i} bar {a} + n sum_{i=1}^{n} a_{i} bar a
       
      
     ans=ni=1∑n​ai2​−2ni=1∑n​ai​aˉ+ni=1∑n​ai​aˉ
 

     
      
       
        
         a
        
        
         n
        
        
         s
        
        
         =
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
         
          2
         
        
        
         −
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
        
        
         
          a
         
         
          ˉ
         
        
       
       
        ans = n sum_{i=1}^{n} a_{i}^2- n sum_{i=1}^{n} a_{i} bar a
       
      
     ans=ni=1∑n​ai2​−ni=1∑n​ai​aˉ
 

     
      
       
        
         a
        
        
         n
        
        
         s
        
        
         =
        
        
         n
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
         
          2
         
        
        
         −
        
        
         (
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
        
        
         
          )
         
         
          2
         
        
       
       
        ans = n sum_{i=1}^{n} a_{i}^2- ( sum_{i=1}^{n} a_{i} )^2
       
      
     ans=ni=1∑n​ai2​−(i=1∑n​ai​)2
 最终化简结果如上。
 
二、操作 
任意选择一个正整数 
    
     
      
       
        1
       
       
        <
       
       
        i
       
       
        <
       
       
        n
       
      
      
       1 < i < n
      
     
    1 画个图观察一下。
 下图为a数组。
 原a[1,2,3,4] = 1,2,4,6(样例数据）
 
 下面看看差分d数组的变化。
 原d[1,2,3] = 1,2,2
 
 肉眼观察，可以发现，当i=2，a[2] = a[1]+a[3]-a[2] = 3
 而d[1]与d[2]的值交换了。
 大胆猜测一下，当操作a[i]时，d[i-1]的值与d[i]的值交换。
 举多几个例子，可以验证这个猜想是正确的。
 也就是说我们可以把差分数组任意重排！！！
 
三、数据分析 
观察题目给的样例
 
 我们再看样例分析
 对于 
    
     
      
       
        (
       
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        
         a
        
        
         3
        
       
       
        ,
       
       
        
         a
        
        
         4
        
       
       
        )
       
       
        =
       
       
        (
       
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        4
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (a_1, a_2, a_3, a_4) = (1, 2, 4, 6)
      
     
    (a1​,a2​,a3​,a4​)=(1,2,4,6)，第一次操作得到的数列有 
    
     
      
       
        (
       
       
        1
       
       
        ,
       
       
        3
       
       
        ,
       
       
        4
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (1, 3, 4, 6)
      
     
    (1,3,4,6)，第二次操作得到的新的数列有 
    
     
      
       
        (
       
       
        1
       
       
        ,
       
       
        3
       
       
        ,
       
       
        5
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (1, 3, 5, 6)
      
     
    (1,3,5,6)。之后无法得到新的数列。
 
对于 
    
     
      
       
        (
       
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        
         a
        
        
         3
        
       
       
        ,
       
       
        
         a
        
        
         4
        
       
       
        )
       
       
        =
       
       
        (
       
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        4
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (a_1, a_2, a_3, a_4) = (1, 2, 4, 6)
      
     
    (a1​,a2​,a3​,a4​)=(1,2,4,6)，平均值为 
    
     
      
       
        
         13
        
        
         4
        
       
      
      
       frac{13}{4}
      
     
    413​，方差为 
    
     
      
       
        
         1
        
        
         4
        
       
       
        (
       
       
        
         
          (
         
         
          1
         
         
          −
         
         
          
           13
          
          
           4
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          2
         
         
          −
         
         
          
           13
          
          
           4
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          4
         
         
          −
         
         
          
           13
          
          
           4
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          6
         
         
          −
         
         
          
           13
          
          
           4
          
         
         
          )
         
        
        
         2
        
       
       
        )
       
       
        =
       
       
        
         59
        
        
         16
        
       
      
      
       frac{1}{4}({(1 - frac{13}{4})}^2 + {(2 - frac{13}{4})}^2 + {(4 - frac{13}{4})}^2 + {(6 - frac{13}{4})}^2) = frac{59}{16}
      
     
    41​((1−413​)2+(2−413​)2+(4−413​)2+(6−413​)2)=1659​。
 
对于 
    
     
      
       
        (
       
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        
         a
        
        
         3
        
       
       
        ,
       
       
        
         a
        
        
         4
        
       
       
        )
       
       
        =
       
       
        (
       
       
        1
       
       
        ,
       
       
        3
       
       
        ,
       
       
        4
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (a_1, a_2, a_3, a_4) = (1, 3, 4, 6)
      
     
    (a1​,a2​,a3​,a4​)=(1,3,4,6)，平均值为 
    
     
      
       
        
         7
        
        
         2
        
       
      
      
       frac{7}{2}
      
     
    27​，方差为 
    
     
      
       
        
         1
        
        
         4
        
       
       
        (
       
       
        
         
          (
         
         
          1
         
         
          −
         
         
          
           7
          
          
           2
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          3
         
         
          −
         
         
          
           7
          
          
           2
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          4
         
         
          −
         
         
          
           7
          
          
           2
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          6
         
         
          −
         
         
          
           7
          
          
           2
          
         
         
          )
         
        
        
         2
        
       
       
        )
       
       
        =
       
       
        
         13
        
        
         4
        
       
      
      
       frac{1}{4} ({(1 - frac{7}{2})}^2 + {(3 - frac{7}{2})}^2 + {(4 - frac{7}{2})}^2 + {(6 - frac{7}{2})}^2) = frac{13}{4}
      
     
    41​((1−27​)2+(3−27​)2+(4−27​)2+(6−27​)2)=413​。
 
对于 
    
     
      
       
        (
       
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        
         a
        
        
         3
        
       
       
        ,
       
       
        
         a
        
        
         4
        
       
       
        )
       
       
        =
       
       
        (
       
       
        1
       
       
        ,
       
       
        3
       
       
        ,
       
       
        5
       
       
        ,
       
       
        6
       
       
        )
       
      
      
       (a_1, a_2, a_3, a_4) = (1, 3, 5, 6)
      
     
    (a1​,a2​,a3​,a4​)=(1,3,5,6)，平均值为 
    
     
      
       
        
         15
        
        
         4
        
       
      
      
       frac{15}{4}
      
     
    415​，方差为 
    
     
      
       
        
         1
        
        
         4
        
       
       
        (
       
       
        
         
          (
         
         
          1
         
         
          −
         
         
          
           15
          
          
           4
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          3
         
         
          −
         
         
          
           15
          
          
           4
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          5
         
         
          −
         
         
          
           15
          
          
           4
          
         
         
          )
         
        
        
         2
        
       
       
        +
       
       
        
         
          (
         
         
          6
         
         
          −
         
         
          
           15
          
          
           4
          
         
         
          )
         
        
        
         2
        
       
       
        )
       
       
        =
       
       
        
         59
        
        
         16
        
       
      
      
       frac{1}{4} ({(1 - frac{15}{4})}^2 + {(3 - frac{15}{4})}^2 + {(5 - frac{15}{4})}^2 + {(6 - frac{15}{4})}^2) = frac{59}{16}
      
     
    41​((1−415​)2+(3−415​)2+(5−415​)2+(6−415​)2)=1659​。
 
由此得知，方差有最小值时的数组为（1,3,4,6）
 我们根据分析操作时的结论，算出此时的差分d数组
 
 咦？好像中间小两边大（满足单谷性质）诶？
 再次举多几个例子，可以发现最优情况下，差分数组都满足单谷性质，这也很容易理解，就不细讲了（严谨证明的话可以用邻值调整法）。
 
四、总结 
到这里，正确思路已经大致出现了。
 将差分数组算出后，进行一个排序，然后依次考虑每一项，要么插在当前最左边，要么插在当前最右边。
 设 
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i][j]
      
     
    dp[i][j] 表示考虑了前 i 个数，当前 
    
     
      
       
        ∑
       
       
        
         a
        
        
         i
        
       
       
        =
       
       
        j
       
      
      
       sum a_i = j
      
     
    ∑ai​=j 的情况下，最小的 
    
     
      
       
        ∑
       
       
        
         a
        
        
         i
        
        
         2
        
       
      
      
       sum a_i^2
      
     
    ∑ai2​ 是多少。
 但是空间限制，我们需要压掉第一维，用滚动数组实现
 

     
      
       
        
         s
        
       
       
        s
       
      
     s数组是记录排序后的差分数组前缀和
 
    
     
      
       
        d
       
       
        p
       
       
        过
       
       
        程
       
      
      
       dp过程
      
     
    dp过程
 放在左边
 插入后的的数组前缀和全部都要加上
    
     
      
       
        d
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       d[i]
      
     
    d[i]
 之前已经放入的数据的和就加上了
    
     
      
       
        i
       
       
        ∗
       
       
        d
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       i*d[i]
      
     
    i∗d[i]
 
    
     
      
       
        那
       
       
        要
       
       
        加
       
       
        上
       
       
        的
       
       
        平
       
       
        方
       
       
        和
       
       
        呢
       
       
        ？
       
      
      
       那要加上的平方和呢？
      
     
    那要加上的平方和呢？
 
     
      
       
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           1
          
         
         
          i
         
        
        
         (
        
        
         
          a
         
         
          j
         
        
        
         +
        
        
         
          d
         
         
          i
         
        
        
         
          )
         
         
          2
         
        
        
         −
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           1
          
         
         
          i
         
        
        
         
          a
         
         
          j
         
         
          2
         
        
       
       
        sum_{j=1}^i (a_j + d_i) ^ 2 - sum_{j=1}^i a_j ^ 2
       
      
     j=1∑i​(aj​+di​)2−j=1∑i​aj2​
 
     
      
       
        
         =
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           1
          
         
         
          i
         
        
        
         (
        
        
         
          a
         
         
          j
         
         
          2
         
        
        
         +
        
        
         2
        
        
         ⋅
        
        
         
          a
         
         
          j
         
        
        
         ⋅
        
        
         
          d
         
         
          i
         
        
        
         +
        
        
         
          d
         
         
          i
         
         
          2
         
        
        
         )
        
        
         −
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           1
          
         
         
          i
         
        
        
         
          a
         
         
          j
         
         
          2
         
        
       
       
        = sum_{j=1}^i (a_j^2 + 2 cdot a_j cdot d_i + d_i ^ 2) - sum_{j=1}^i a_j^2
       
      
     =j=1∑i​(aj2​+2⋅aj​⋅di​+di2​)−j=1∑i​aj2​
 
     
      
       
        
         =
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           1
          
         
         
          i
         
        
        
         (
        
        
         2
        
        
         ⋅
        
        
         
          a
         
         
          j
         
        
        
         ⋅
        
        
         
          d
         
         
          i
         
        
        
         +
        
        
         
          d
         
         
          i
         
         
          2
         
        
        
         )
        
       
       
        = sum_{j=1}^i (2 cdot a_j cdot d_i + d_i^2)
       
      
     =j=1∑i​(2⋅aj​⋅di​+di2​)
 
     
      
       
        
         =
        
        
         2
        
        
         ⋅
        
        
         
          d
         
         
          i
         
        
        
         ⋅
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           1
          
         
         
          i
         
        
        
         
          a
         
         
          j
         
        
        
         +
        
        
         i
        
        
         ⋅
        
        
         
          d
         
         
          i
         
         
          2
         
        
       
       
        = 2 cdot d_i cdot sum_{j=1}^i a_j + i cdot d_i ^ 2
       
      
     =2⋅di​⋅j=1∑i​aj​+i⋅di2​
 所以只要实时记录一下 
    
     
      
       
        
         ∑
        
        
         
          j
         
         
          =
         
         
          1
         
        
        
         i
        
       
       
        
         a
        
        
         j
        
       
      
      
       sum_{j=1}^i a_j
      
     
    ∑j=1i​aj​ 就OK了。
 

     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         j
        
        
         +
        
        
         i
        
        
         ∗
        
        
         d
        
        
         [
        
        
         i
        
        
         ]
        
        
         ]
        
        
         =
        
        
         m
        
        
         i
        
        
         n
        
        
         (
        
        
         d
        
        
         p
        
        
         [
        
        
         j
        
        
         +
        
        
         i
        
        
         ∗
        
        
         d
        
        
         [
        
        
         i
        
        
         ]
        
        
         ]
        
        
         ,
        
        
         d
        
        
         p
        
        
         [
        
        
         j
        
        
         ]
        
        
         +
        
        
         2
        
        
         ∗
        
        
         d
        
        
         [
        
        
         i
        
        
         ]
        
        
         ∗
        
        
         j
        
        
         +
        
        
         i
        
        
         ∗
        
        
         d
        
        
         [
        
        
         i
        
        
         ]
        
        
         ∗
        
        
         d
        
        
         [
        
        
         i
        
        
         ]
        
        
         )
        
       
       
        dp[j+i*d[i]] = min(dp[j+i*d[i]],dp[j]+2*d[i]*j+i*d[i]*d[i])
       
      
     dp[j+i∗d[i]]=min(dp[j+i∗d[i]],dp[j]+2∗d[i]∗j+i∗d[i]∗d[i])
 
放在右边
 总和要加上已经进入数组的前缀和，
 平方和也只需加上新插入的平方，很好理解
 
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         j
        
        
         +
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
        
         ]
        
        
         =
        
        
         m
        
        
         i
        
        
         n
        
        
         (
        
        
         d
        
        
         p
        
        
         [
        
        
         j
        
        
         +
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
        
         ]
        
        
         ,
        
        
         d
        
        
         p
        
        
         [
        
        
         j
        
        
         ]
        
        
         +
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
        
         ∗
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
        
         )
        
       
       
        dp[j+s[i]] = min(dp[j+s[i]],dp[j]+s[i]*s[i])
       
      
     dp[j+s[i]]=min(dp[j+s[i]],dp[j]+s[i]∗s[i])
 
AC代码 
#include
#include
#include
#include
#include
#include
using namespace std;
int a[10010],d[10010],s[10010],n,ss;
long long dp[500100],ans,lim;
const long long inf = 1e12;
long long minn(long long a,long long b){
	return a<=b ? a : b;
}
int main(){
//	freopen("variance.in","r",stdin);
//	freopen("variance.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=2;i<=n;i++){
		d[i-1] = a[i]-a[i-1];
	}
	sort(d+1,d+n);
	for(int i=1;i
		s[i] = s[i-1] + d[i];
	}
	lim = n*a[n];
	for(int i=0;i<=lim;i++){//初始化
		dp[i] = inf;
	}
	dp[0] = 0;
	for(int i=1;i
		if(!s[i]) continue;
		for(int j=lim;j>=0;j--){
			if(dp[j]==inf) continue;
			dp[j+s[i]] = minn(dp[j+s[i]],dp[j]+s[i]*s[i]);//放在右边
			dp[j+i*d[i]] = minn(dp[j+i*d[i]],dp[j]+2*d[i]*j+i*d[i]*d[i]);//放在左边
			dp[j] = inf;
		}
	}
	ans = inf;
	for(long long i=0;i<=lim;i++){
		if(dp[i]==inf) continue;
        ans=minn(ans,n*dp[i]-i*i);
	}
	printf("%lld",ans);
//	fclose(stdin);
//	fclose(stdout);
	return 0; 
}
 
作者的第一篇题解，若有不足，欢迎提出建议。