ζ

CF1674E-Breaking the Wall

    题解

题目大意:给定一个数组a,一次操作可以任意选择一个i,令a[i]=a[i]-2, a[i-1]=a[i-1]-1, a[i-2]=a[i-2]-1。问至少需要多少次操作,可以使数组中出现至少两个小于或等于0的元素。

从结果出发逆向思考。最终被减小到0以下的两个元素的位置关系有下列三种情况:

  1. 两个元素之间间隔的元素多余1个。这种情况下的最优做法是分别使两个元素每次-2。
  2. 两个元素之间没有间隔。这种情况下的最优做法是一直使较高的元素-2,直到两个元素都等于0.
  3. 两个元素之间间隔一个元素。这种情况下,由于每次减少的个数为2,如果两个元素初始状态下都为奇数,那么就先在它们中间打一下,使它们都变成偶数,再对它们实行与情况1相同的操作方法,否则直接实行第一种情况的打法就行了。

数据范围允许暴力求得这三种情况所需的的最少操作数,求出来后比较就行了。

页阅读量:  ・  站访问量:  ・  站访客数: