A题题意:有n堆东西,和d天时间,我们可以每天将某堆x的东西中的1份,搬去相邻的堆也就是可以搬去第x-1堆上或者第x+1堆上。然后求d天之后第一堆上东西最多有多少份。
思路:贪心的想,我们肯定先把靠近第一堆上的东西先搬去第一堆,然后再去看更远的堆,所以只需要从第2堆开始,只要还有时间,就把堆上的东西搬去第一堆,直到天数花光为止。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 100010; int n,m,t,k,ans,r,l; int main(){ cin>>t; while(t--){ cin>>n>>m; ans = 0; int a[N]; for(int i = 0;i < n ;i++){ cin>>a[i]; } ans=a[0]; for(int i = 1 ;i < n ;i++){ if(m<=0) break; if(a[i]>0){ if(i*a[i]>=m){ ans+=(m/i); break; }else{ ans+=(a[i]); m-= (i*a[i]); } } } cout<<ans<<endl; } return 0; }
B题题意:把某人放在一个平面直角坐标系里,这个人有自己喜欢的几个数字,然后他想从(0,0)前往(0,x),但是他只能通过跳跃的方式,每次跳一段距离,这个距离必须得是他喜欢的数字之一,现在需要求他最少跳几次能到达目标点。
思路:考虑到跳的次数最少,所以每一次跳的要尽可能远,但是又必须准确跳到坐标(0,x)上,而根据三角形的知识,我们完全可以利用最长边跳两次来构造出一个范围小于2*max的边,所以我们完全只需要用到最长边来构造答案。但是要考虑到特殊情况,也就是存在一跳直接跳到终点的情况。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 100010; int n,m,t,k,ans,r,l; int a[N]; int main(){ cin>>t; while(t--){ cin>>n>>m; for(int i = 0 ;i < n ;i ++){ cin>>a[i]; } sort(a,a+n); k = n-1; while(a[k]>m && k>0){ k--; } if(a[k] == m) ans = 1; else{ ans = max(2,(m+a[n-1]-1)/a[n-1]); } cout<<ans<<endl; } return 0; }
Codeforces Round #621 (Div. 1 + Div. 2) A-C题解
原文:https://www.cnblogs.com/Flydoggie/p/12329099.html