强烈建议你试试无所不能的chatGPT，快点击我

纪中12日T1 2307. 选择

阅读量：5273 次

发布时间：2019-06-14

本文共 2783 字，大约阅读时间需要 9 分钟。

2307. 选择

(File IO): input:choose.in output:choose.out

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述

输入

输出

样例输入

样例输出

数据范围限制

提示

【样例解释】

样例一：L = 1， R = 3 样例二：L = 2， R = 5

Solution

题目恶心到我能看懂

Algorithm（n³）

枚举l，枚举r，枚举i∈[l,r]；累加sum，minans打擂台

Code（≌0分）

#include
      
       //不想OI一场空，千万别用万能头#include
       
        //快排sort()#include
        
         //能不用cin就不用#include
         
          #include
          #include
           
            #define IL inlineusing namespace std;IL void fin(){freopen("choose.in","r",stdin);}IL void fout(){freopen("choose.out","w",stdout);}IL void fio(){ fin(); fout();}int n,a[300002],b[300002],ans,minans=0x3f3f3f3f;int main(){// fio(); cin>>n; for(int i=0;i

n3

Algorithm（n²）

枚举l，枚举r；sum动态变化，minans打擂台

Code（20分）

#include
      
       //不想OI一场空，千万别用万能头#include
       
        //能不用cin就不用#include
        
         #include
         #include
          
           #define IL inlineusing namespace std;IL void fin(){freopen("choose.in","r",stdin);}IL void fout(){freopen("choose.out","w",stdout);}IL void fio(){    fin();    fout();}int n,a[300002],b[300002];long long minans=0x3f3f3f3f3f,ans,l,r;int main(){    fio();    cin>>n;    for(int i=0;i

n2

Algorithm（nlog（n））

这才是重点……

一个suma存a的前缀和

一个sumb存b的前缀和

一个diff存suma-sumb

于是内存10MB起步

为了省空间

我又修改了一遍再提交；

在每个循环（i：1 to n）中，

suma[i]=sum[i-1]+a[i]

sumb[i]=sum[i-1]+b[i]

diff[i]=suma[i]-sumb[i]

=suma[i-1]+a[i]-(sumb[i-1]+b[i])

=suma[i-1]-sumb[i-1]+a[i]-b[i]

=diff[i-1]+a[i]-b[i]

于是我就省了许多空间（甚至连数组b都可以不要滴）

10MB->5MB

150ms->105ms

Code（100分）

//10MB部分即为注释#include
     
      //不想OI一场空，千万别用万能头#include
      
       //快排sort()#include
       
        //能不用cin就不用#include
        
         #include
         #define IL inlineusing namespace std;IL void fin(){freopen("choose.in","r",stdin);}IL void fout(){freopen("choose.out","w",stdout);}IL void fio(){    fin();    fout();}long long n,a[300001],b/*[300001]*/,ans,minans=0x3f3f3f,/*suma[300002],sumb[300002],*/diff[300001];int main(){    fio();    cin>>n;    for(int i=1;i<=n;i++)     {        scanf("%lld",a+i);//        suma[i]=suma[i-1]+a[i];    }    for(int i=1;i<=n;i++)     {        scanf("%lld",&b/*+i*/);//        sumb[i]=sumb[i-1]+b[i];        diff[i]=diff[i-1]+a[i]-b/*[i]*/;        /*        diff[i]=suma[i]-sumb[i];        diff[i]=suma[i-1]+a[i]-sumb[i-1]-b[i];        diff[i]=diff[i-1]+a[i]-b[i];        */    }    sort(diff,diff+n+1);    for(int i=1;i<=n;i++)        minans=min(minans,abs(diff[i]-diff[i-1]));    cout<

Attention

sort从0开始！（就算diff只用了1~n）

因为diff可能保存负值

diff[0]=0 如果不参加排序，diff[1]-diff[0]岂不还是diff[0]，与我们的目的偏离甚远？

不如就让0参加排序嘛

这也代表着：l==0时的情况

另外

数组和minans开long long！

数组和minans开long long！

数组和minans开long long！

否则满分80分，（扣20分起步）……

转载于:https://www.cnblogs.com/send-off-a-friend/p/11340682.html

你可能感兴趣的文章

HDU 3949：XOR（高斯消元+线性基）

next_permutation()—遍历全排列

Web设计的十大错误

BSP:bootstrap导航栏：navbar,navbar-default,collapse

【洛谷2304_LOJ2134】[NOI2015]小园丁与老司机（动态规划_网络流）

linux下清除tomcat缓存

WPF自定义仪表盘控件

WPF绘制折线

VS2017MVC+EF+MySQL环境搭建

利用OpacityMask制作打洞效果

visualsvn server 提交修改日志

WPF 自定义键盘焦点样式（FocusVisualStyle）

使用Data Annotations进行手动数据验证

WebSocket和Socket

x名称空间中的内容

【ASP.NET Core】浅说目录浏览

用树莓派做一个离线下载机

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-11-25 20:47:17 当前IP: 3.141.21.199 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我