dd爱框框

链接dd爱框框

题目解析

这道题的意思是在1到n的区间里我们要求出里面的最小区间,使得区间里的所有数加起来大于或等于x,比如区间[1,5]意思就是从arr[1]开始一直到arr[5]的所有数据,[5,8]就表示从arr[5]到arr[8],需要注意这里的n个数是从1开始的,所以用数组的时候我们要先从1开始输入

解析

我们以图中示例为例

输出3 5表示区间[3,5]中的所有数据加起来大于等于x,且这个区间的长度相比于后面的区间长度来说是最小的

代码

方法一暴力解法

暴力解法就是给一个left和right让right和left相加,当结果大于等于x的时候就记录下来

这里的范围是[1,5],然后left往后移动,之后right=left,然后right往后走

方法二同向双指针(滑动窗口)

这个方法是在方法一的基础上进行优化
比如left在1的时候,范围是[1,5],在这个范围的总和为27,之后left++
但是right是没有必要重新会到left位置再往后去确定范围,因为left在a[1]的时候right在a[5]是刚好满足条件的,那么left++后来到a[2]时[2,5]的所以数总和只会比[1,5]少一个a[1],所以只需要在[1,5]总和减去一个a[1]就可以了

然后判断减去a[1]后[2,5]是否满足>=x的条件
这个方法的流程如下

#include using namespace std; const int N=1e7+10; int arr[N]; int n,x; int main() {     cin>>n>>x;     for(int i=1;i<=n;i++)          cin>>arr[i];     int left=0,right=0,sum=0;     int retLen=N,retLeft=-1,retRight=-1;     while(right<=n)     {         sum+=arr[right];         while(sum>=x)         {             if(right-left+1                 retLeft=left;                 retRight=right;                 retLen=right-left+1;             }             sum-=arr[left++];         }         right++;     }     cout<

#include #include using namespace std;     typedef long long LL; LL n,k; priority_queue heap; int main() {     cin>>n>>k;     LL sum=0,x;     while(n--)     {         cin>>x;         sum+=x;         if(x%2==0)             heap.push(x);     }     while(heap.size()&&k--)     {         LL t=heap.top()/2;         heap.pop();         sum-=t;         if(t%2==0)             heap.push(t);     }     cout<