C. Water the Trees
题意：给出n颗树的高度，在一天内你可以选择浇树或者不浇，偶数天浇树树长高2，奇数为1
问最短天数使所有树都一样高
*** 作如下 :
如果是奇数天,可以给树浇水使得树h[i]+1 , 如果是偶数天,可以给树浇水使得树h[i]+2
你也可以不浇水,一天只能浇一颗,看到这种最小的… 考虑直接 二分天数
首先所有数至少都要加到maxn里面,但是加到maxn不一定最优,因此我们还需要考,maxn+1,maxn+2,我们如何check呢 ?
首先 :
能+ 2 的次数mid/2 ,能+ 1 的次数mid−mid/2
然后我们计算每个h [ i ] ,需要加多少次2 ,然后再用计算出来的 t 2 ，计算出需要1的次数,即不足用1 补
输入样例
3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4
输出样例
4
3
16
#include
using namespace std;
typedef long long ll;
const int N=3e5+10;
ll a[N],n;
int t;
bool check(ll day,ll high)
{
ll time2=day/2;
ll time1=day-time2;
for(int i=0;i=0;
}
void solve()
{
ll maxn=-1;
scanf("%lld",&n);
for(int i=0;i 题意：给一个长度为n的数组b，和一个初始化为0的a数组。
给出一种 *** 作选取长度为k的区间从左到右每个数加分别加1，2，3...k，问最少 *** 作次数使a数组每个位置的值大于等于b
贪心 对于一个1-（k+1）的区间我们先对2-（k+1）做 *** 作使k+1位置的数满足条件再对1-k做 *** 作肯定比反过来次数要少，所以从后往前去贪心是可行的，然后对于每个位置用k去加一定是最快的
#include
using namespace std;
#define int long long
const int N=3e5+7;
int a[N],b[N];
signed main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>b[i];
int ans=0,cnt=0,add=0;
for(int i=n;i>=1;i--)
{
add-=cnt;//每次前面一个数都比后一个小1，一共有cnt *** 作作用在这两个数上
if(i<=n-k) cnt-=a[i+k];//对于前一个数来说i+k的操作已经影响不到了所以减去
int t=min(i,k);//对于前k个点最大只能加i
if(add
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）