大连微网站制作,wordpress 暗箱,天元建设集团有限公司信息,网站建设技术培训C. Pekora and Trampoline
题意#xff1a;对于数组a#xff0c;每次出发开始可以选择任意元素作为起始点#xff0c;然后在数组上移动#xff0c;落点为i a[i]#xff0c;直至超出数组范围#xff0c;每次经过的点的值减一#xff08;先移动再减/直至减到1为止#…C. Pekora and Trampoline
题意对于数组a每次出发开始可以选择任意元素作为起始点然后在数组上移动落点为i a[i]直至超出数组范围每次经过的点的值减一先移动再减/直至减到1为止求使数组元素全为1所用最少的出发次数
数据范围数组大小n:[1,5000][1,5000][1,5000] 元素大小 a[i]:[1,109][1,10^9][1,109]
思路模拟优化 首先观察元素大小的最大值远高于数组大小上限此时站在上面会直接超出数组范围直接模拟会多次重复该动作消耗大量时间因此可以对其超出数组范围的部分批量一次性处理 再者是数组不断趋向全为1的状态中间态的数组难免出现大量的连续的1直接模拟经过连续1时只能一步步走则会消耗大量时间因此可以另开一个数组去对应记录当该值为1时最终会跳那个非1的值的位置
#includeiostream
#includevector
#includealgorithm
#includecmath
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
const int N 5010;
int a[N], n;
using namespace std;void SetLeft(vectorint b, int j) //当数组出现新的1时去更新该1及相邻的左边的1的跳转点
{b[j] b[j 1];for (int i j - 1; i 1; i--){if (a[i] 1) b[i] b[i 1];else return;}
}int main()
{fastio();int t;cin t;while (t--){cin n;for (size_t i 1; i n; i) cin a[i];ll ans 0;vectorint b(n 2);b[n 1] n 1; //使最后一个元素a[n]为1时跳到n1即超出数组范围for (int i n; i 1; i--){if (a[i] ! 1) b[i] i;else b[i] b[i 1];}while (1){int beg b[1]; //每次从最左端出发最优性待证明if (beg n) break; //此时说明数组全为1if (a[beg] max(n - beg, 1)) //批量处理超出数组范围的部分{ans a[beg] - max(n - beg, 1); //max函数避免当begn时出现0a[beg] max(n - beg, 1);if (a[beg] 1) SetLeft(b, beg);continue;}int j beg, k;while (j n){if (a[j] 1) k b[j]; //元素为1时快速跳转else k j a[j];if (a[j] 2) SetLeft(b, j); //此时说明将数组出现新的1a[j] max(a[j] - 1, 1);j k; }ans;}cout ans \n;}return 0;
}
