Codeforces Round #555 (Div. 3) D. N Problems During K Days 【数学思维】

一 题面

  D. N Problems During K Days

二 分析

  对于这题,刚开始我就是陷入了对公式的执着,企图用公式直接确定第一个数,然后试着去找序列。经过思考和手动模拟后发现是很难保证正确性的。

  对于这题,第一步是很明确的,就是确定第一个数,如果给定了$N$和$K$,那么第一个数是可以确定的。因为如果我们只保证后一个数比当前数多1,并且确定第一个数是1,那么可以根据$K$确定对应的最小和$sum$

$sum = \frac{K(K+1)}{2}$

这个公式应该比较基础。这样我们就可以把$N<sum$的情况就全部排除掉了。

  接下来,分析确定的$K$和$N>=sum$的情况:

  首先,可以确定一个公式

$N - sum = {K}\times{t} + res$  $res<K$

这个公式也比较基础。

  有了这个公式后,就比较明了了,因为可以在$sum$的基础上把$t$个$K$平摊掉,就是对应的$K$个数每个数加1。

  接下来处理$res$,这里可能需要动脑袋思考一下。但我们依然需要明确,第一个数是不可以改变的,因为第一个数改变了会直接影响后面的所有数。

  处理$res$,我们可以直接从当前确定的数组从后往前进行加操作,操作的前提是满足题目给定的条件。加了之后会发现,如果当前的数加了一个数后,那么右边已经加过的数范围又变了,又可以加了,但是是有限度的,因为第一个数已经确定了。(这里也提醒了我们为什么不从左往右进行处理)

  处理$res$的时候,如果出现了遍历一遍后,$res > 0$并且没有加数的情况,就表示数组已经无法满足题目给定的条件了,直接输出$NO$即可。

 

三 AC代码

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define LL long long
 5 const int MAXN = 1e5 + 15;
 6 int N;
 7 LL K;
 8 int Data[MAXN];
 9 
10 int main()
11 {
12     ios::sync_with_stdio(false);
13     cin >> N >> K;
14     //第一个数为1的最基础的情况
15     LL sum = (K * (K + 1) ) >> 1;
16     if(sum > N)
17     {
18         cout << "NO" << endl;
19         return 0;
20     }
21     N -= sum;
22     int res = N % K;
23     Data[1] = 1 + N/K;
24     for(int i = 2; i <= K; i++)
25         Data[i] = Data[i - 1] + 1;
26     //满足最低要求后,还剩下res < k
27     while(res)
28     {
29         bool flag = true;
30         //第一个数一定不能变
31         for(int i = K; i > 1; i--)
32         {
33             int tmp = (Data[i -1 ] << 1 ) - Data[i];
34             if( res > 0 && tmp > 0)
35             {
36                 //数组中有数变化了
37                 flag = false;
38                 if(res >= tmp)
39                 {
40                     Data[i] += tmp;
41                     res -= tmp;
42                 }
43                 else
44                 {
45                     Data[i] += res;
46                     res = 0;
47                 }
48             }
49         }
50         if(flag)
51         {
52             cout << "NO" << endl;
53             return 0;
54         }
55     }
56     cout << "YES" << endl;
57     for(int i = 1; i < K; i++)
58     {
59         cout << Data[i] << " ";
60     }
61     cout << Data[K] << endl;
62     return 0;
63 }

 

上一篇:【LeetCode】20. 有效的括号


下一篇:Big Problems for Organizers CodeForces - 418D (贪心,直径)