题解

29 条题解

  • 2
    @ 2018-08-20 09:16:25
    /*
    20%的数据:随便搞搞
    40%的数据:同上
    60%的数据:枚举N次,每次枚举每一户人家,判断这一户人家是否被推销过,
    找到选择哪一户人家会得到最大的疲劳值,累加到ans里即可。
    注意:若选择在当前已选最靠右的一户人家(设为x)的左边的人家(设为y),
    则答案只需要增加推销这户人家的疲劳值(即ans=ans+A[y])。
    而选择x右边的人家(设为z),则答案需要增加多出来的走路疲劳值和推销这户人家的疲劳值
    (即ans=ans+(d[z]-d[x])*2+A[z])。时间复杂度O(n2)
    100%的数据:和60分数据差不多,
    将枚举每一户人家改为用堆维护已选的最右边的那户人家(设为x)的左边推销疲劳值的最大值(
    设为堆D1)和x的右边推销疲劳值加上来回走路疲劳值的最大值(设为堆D2)。
    那么每次的答案就是ans=ans+max(D1[1],D2[1]-d[x]*2)。
    求答案之前要判断D1[1]和D2[1]是否合法
    (即D1[1]所对应的点在x左边且没选过,D2[1]所对应的点在x的右边且没选过)。
    时间复杂度O(n log2 n)。
    做模拟比赛的时候想了半天
    想到了线段树?
    然后线段树没有滑稽币不会啊
    然后就果断打了个60分暴力QAQ
    然后考完一看
    这个堆优化不是很容易想到吗
    唉果然被普及组吓坏了
    都不敢想高级算法了直接交了个暴力
    Orz我好害怕
    说说我的理解吧
    我们很容易看到
    其实对于选择n个这个问题
    可以贪心的
    不难想到 X= i 时的最优方案一定从 X = i-1 时的最优方案的基础上再加一户宣传对象得来。
    考虑 X = 1 时的选择,显然是所有住户中 Ai + 2Si 中最大的被选,
    若有多个住户的 Ai + 2Si 相同,则优先选择 Si 最小的(想一想为什么)。
    然后序列被划分成左右两个部分,选择左边住户获得 Ai 的贡献,
    选择右边住户获得 Ai + 2(Si - T) 的贡献,T 表示当前划分界限到胡同入口的距离,
    注意右边部分的贡献的大小关系相比最初并没有改变,只需要重新对左边住户的贡献进行排序。
    于是可以建一个新优先队列将左边的所有住户加入,将原优先队列中被划分到左边部分的元素丢掉。
    因为划分界线是一直往右移的,所以每个元素至多被加入两次,被删除两次,
    说白了就是我们每次选一个最优
    只有可能是两种情况
    1.继续向右走扩大距离(这个情况肯定是要选择能得到最大疲劳值的点)
    2.不继续向右走了(那么我们就直接在左边选一个推销疲劳值的最大的点了)
    两种情况去最大就好了
    考虑到范围很大
    加了个堆(优先队列)优化咯
    Orz就这样没了
    */
    #include <cstdio>
    #include <queue>
    using namespace std;
    
    const int MAXN=100010;
    int d[MAXN],a[MAXN];
    int Last,Next,n,Sum,Best;
    priority_queue<int> q;//堆用来维护已选的最右边的点左边的最大值
    
    void init()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&d[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
    }
    
    void solve()
    {
        Next=0;//Next用来记录下下一个最右边点的位置
        for(int k=1;k<=n;k++)
        {
            Last=Next;//已选的最右边的点
            if(!q.empty())//q非空(即不是第一次)
                Best=q.top()+d[Last]*2;//因为sum中只保存了所有选取的疲劳值而为保存走路的疲劳值
                                       //就是直接选取了左边的最优解
            else 
                Best=0;
            for(int i=Last+1;i<=n;i++)//尝试右边可不可以更新最大疲劳值
                if(a[i]+d[i]*2>Best)
                {
                    Best=a[i]+d[i]*2;
                    Next=i;//记录下更新的右边的店
                }
            printf("%d\n",Sum+Best);
            if(Next==Last)//如果没有更新到最右边的点
            {
                Sum+=q.top();//就直接选取堆中的点
                q.pop();//选完了出栈
            }
            else//说明选取的是右边的点
            {
                for(int i=Last+1;i<Next;i++)//更新了最右边的点那么左边的点要跟到来入栈
                    q.push(a[i]);
                Sum+=a[Next];//选上了这个点
            }
        }
    }
    
    int main()
    {
        init();
        solve();
        return 0;
    }
    
  • 2
    @ 2017-07-26 11:35:21

    相同的代码,codeVS上满分,这里10分。。。
    还又WA又T。。。
    求大神帮忙看看有什么问题

    #include<bits/stdc++.h>
    using namespace std;
    int a[100100],b[100100];
    bool f[100100];
    int maxi,len1,len2;
    struct node{
    int id;
    int sum;
    }c[100100],d[100100];
    int cmp(node x,node y){
    return x.sum<y.sum;
    }
    void built1(int beg,int en){
    len1=0;
    for(int i=beg;i<=en;i++)
    if (f[i]==true){
    c[i-beg+1].id=i;
    c[i-beg+1].sum=b[i];
    len1++;
    }
    make_heap(c+1,c+len1+1,cmp);
    }
    void built2(int beg,int en){
    len2=0;
    for(int i=beg;i<=en;i++)
    if (f[i]==true){
    d[i-beg+1].id=i;
    d[i-beg+1].sum=b[i]+(a[i]-a[maxi])*2;
    len2++;
    }
    make_heap(d+1,d+len2+1,cmp);
    }
    int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    maxi=1;
    for(int i=1;i<=n;i++){
    cin>>b[i];
    if(a[i]*2+b[i]>a[maxi]*2+b[maxi]) maxi=i;
    }
    memset(f,true,sizeof(f));
    int total=a[maxi]*2+b[maxi];
    cout<<total<<endl;
    f[maxi]=false;
    built1(1,maxi-1);
    built2(maxi+1,n);
    int left=1;int right=n;
    for(int i=1;i<n;i++){
    int p,pmax;
    int q,qmax;
    pmax=c[1].sum;p=c[1].id;
    qmax=d[1].sum;q=d[1].id;
    int xb,m;
    if (pmax>qmax){
    xb=p;
    m=pmax;
    pop_heap(c+1,c+len1+1,cmp);
    len1--;
    }else{
    xb=q;
    maxi=q;
    m=qmax;
    f[q]=false;
    built1(left,maxi-1);
    built2(maxi+1,right);
    }
    total+=m;
    f[xb]=false;
    while(f[left]==false) left++;
    while(f[right]==false) right--;
    cout<<total<<endl;
    }
    return 0;
    }

    #1 Accepted 2ms 384.0KiB
    #2 Wrong Answer 3ms 464.0KiB
    #3 Wrong Answer 3ms 384.0KiB
    #4 Wrong Answer 3ms 384.0KiB
    #5 Wrong Answer 13ms 500.0KiB
    #6 Wrong Answer 2ms 384.0KiB
    #7 Wrong Answer 59ms 1.375MiB
    #8 Time Exceeded ≥1005ms ≥1.691MiB
    #9 Time Exceeded ≥1003ms ≥2.621MiB
    #10 Time Exceeded ≥1001ms ≥1.965MiB

    测试点#salesman1.in 结果:AC 内存使用量: 360kB 时间使用量: 1ms
    测试点#salesman10.in 结果:AC 内存使用量: 3692kB 时间使用量: 310ms
    测试点#salesman2.in 结果:AC 内存使用量: 360kB 时间使用量: 1ms
    测试点#salesman3.in 结果:AC 内存使用量: 364kB 时间使用量: 1ms
    测试点#salesman4.in 结果:AC 内存使用量: 360kB 时间使用量: 1ms
    测试点#salesman5.in 结果:AC 内存使用量: 364kB 时间使用量: 2ms
    测试点#salesman6.in 结果:AC 内存使用量: 364kB 时间使用量: 3ms
    测试点#salesman7.in 结果:AC 内存使用量: 3944kB 时间使用量: 319ms
    测试点#salesman8.in 结果:AC 内存使用量: 3948kB 时间使用量: 299ms
    测试点#salesman9.in 结果:AC 内存使用量: 3692kB 时间使用量: 299ms

  • 1
    @ 2018-11-08 18:52:43

    rkbudlo大神的天才思路
    你们写的都好多

    #include<bits/stdc++.h>
    using namespace std;
    int Maxs[100005],Max[100005],sum[100005],n;
    struct tzg{int s,x;}a[100005];
    bool cmp(tzg x,tzg y){return x.x>y.x;}
    int max(int x,int y){return x>y?x:y;}
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)scanf("%d",&a[i].s);
        for(int i=1;i<=n;++i)scanf("%d",&a[i].x);
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i].x;
        for(int i=1;i<=n;++i)Maxs[i]=max(Maxs[i-1],a[i].s);
        for(int i=n;i>=1;--i)Max[i]=max(Max[i+1],a[i].s*2+a[i].x);
        for(int i=1;i<=n;++i)printf("%d\n",max(sum[i-1]+Max[i],sum[i]+Maxs[i]*2));
        return 0;
    }
    
  • 1
    @ 2016-11-09 15:42:37

    用堆做的,程序在我校的标准数据中是通过的,然而vj不知为啥不过,求指点
    编译成功

    Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
    Copyright (c) 1993-2015 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    foo.pas(44,32) Warning: range check error while evaluating constants (-1 must be between 0 and 4294967295)
    foo.pas(4,10) Note: Local variable "tmax" not used
    Linking foo.exe
    72 lines compiled, 0.0 sec, 28240 bytes code, 1268 bytes data
    1 warning(s) issued
    1 note(s) issued

    测试数据 #0: Accepted, time = 0 ms, mem = 3940 KiB, score = 10

    测试数据 #1: WrongAnswer, time = 0 ms, mem = 3940 KiB, score = 0

    测试数据 #2: WrongAnswer, time = 0 ms, mem = 3940 KiB, score = 0

    测试数据 #3: Accepted, time = 15 ms, mem = 3940 KiB, score = 10

    测试数据 #4: WrongAnswer, time = 15 ms, mem = 3940 KiB, score = 0

    测试数据 #5: Accepted, time = 0 ms, mem = 3936 KiB, score = 10

    测试数据 #6: RuntimeError, time = 31 ms, mem = 3936 KiB, score = 0

    测试数据 #7: RuntimeError, time = 31 ms, mem = 3940 KiB, score = 0

    测试数据 #8: RuntimeError, time = 46 ms, mem = 3940 KiB, score = 0

    测试数据 #9: RuntimeError, time = 31 ms, mem = 3940 KiB, score = 0

    RuntimeError, time = 169 ms, mem = 3940 KiB, score = 30
    代码
    ```pascal
    //const bind=array[0..200001] of longint;
    var //heap:bind;
    heap,jli,pl,ans:array[0..200001] of longint;
    i,j,len,tmax,ti,li,n:longint;

    procedure swap(var a,b:longint);
    var t:longint;
    begin t:=a;a:=b;b:=t;end;

    procedure put(a:longint);
    var i:longint;
    begin
    inc(len);
    heap[len]:=a;
    i:=len;
    while (heap[i]>heap[i>>1])and(i<>1) do begin
    swap(heap[i],heap[i>>1]);
    i:=i>>1;
    end;
    end;

    function get:longint;
    var i,t:longint;
    begin
    get:=heap[1];
    heap[1]:=heap[len];
    heap[len]:=-1;
    dec(len);i:=1;
    if len=0 then exit;
    while true do begin
    t:=i<<1;
    if (heap[i]<heap[t])and(heap[t]>heap[t+1])and(heap[t]<>-1)then begin
    swap(heap[i],heap[t]);i:=t;end
    else if (heap[i]<heap[t+1])and(heap[t+1]<>-1)then begin
    swap(heap[i],heap[t+1]);i:=t+1;end
    else break;
    end;
    end;

    begin
    //assign(input,'salesman.in'); assign(output,'salesman.out');
    //reset(input); rewrite(output);
    read(n);
    filldword(heap,length(heap),-1);
    //filldword(d2,length(d2),maxlongint);
    //le[0]:=0;
    for i:=1 to n do read(jli[i]);
    for i:=1 to n do read(pl[i]);
    //l1:=0;l2:=0;
    //ans[1]:=get(d2,l2,l1);
    ans[1]:=pl[n]+jli[n]<<1;
    li:=1;ti:=n;
    for j:=n-1 downto 1 do if pl[j]+jli[j]<<1>ans[1] then begin
    ans[1]:=pl[j]+jli[j]<<1;ti:=j;
    end;
    for i:=1 to ti-1 do put(pl[i]);
    li:=ti;
    //for j:=1 to len do write(heap[j],' ');writeln;
    writeln(ans[1]);

    for i:=2 to n do begin
    //writeln('li=',li);
    ans[i]:=0;
    for j:=n downto li+1 do if pl[j]+(jli[j]-jli[li])<<1>ans[i] then begin
    ans[i]:=pl[j]+(jli[j]-jli[li])<<1;ti:=j;//writeln('le');
    end;
    for j:=li+1 to ti-1 do put(pl[i]);//if i=5 then writeln(ans[i]);
    if (heap[1]>ans[i]) then ans[i]:=get else li:=ti;
    //for j:=1 to 5 do write(heap[j],' ');writeln;
    inc(ans[i],ans[pred(i)]);writeln(ans[i]);
    end;
    //close(input); close(output);
    end.
    ```

  • 0
    @ 2017-08-12 14:37:51

    大神们能帮我看看么??少了第一个输出
    #include <iostream>
    #include <iomanip>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <algorithm>
    #include <queue>
    #include <set>
    #include <map>
    #include <stack>
    #include <vector>
    #include <list>
    #include <cstdio>
    #include <deque>
    #include <cstring>
    #include <stdlib.h>

    using namespace std;
    int comp(int a,int b)
    {
    return a>b;
    }
    int main()
    {
    freopen("salesman.in","r",stdin);
    freopen("salesman.out","w",stdout);
    long n,tie[100000],pt[100000],sum[100000],pp[100000],s;
    cin>>n;
    for(int i=1;i<=n;++i)
    cin>>pt[i];
    for(int i=1;i<=n;++i)
    {
    cin>>tie[i];
    pt[i]=pt[i]*2+tie[i];
    }
    for(int i=2;i<=n;++i)
    {
    for(int l=1;l<=n;++l)
    pp[l]=tie[l];
    for(int k=i;k<=n;++k)
    {
    sort(pp+1,pp+k-1,comp);
    for(int j=1;j<=i-1;++j)
    s=s+pp[j];
    sum[k]=pt[k]+s;
    s=0;
    }
    sort(sum+i,sum+n,comp);
    cout<<sum[i]<<endl;
    memset(sum,0,sizeof(sum));
    }
    return 0;
    }

  • 0
    @ 2017-08-04 13:00:50
    
    Var
         i,j:longint;
         max,num,n:int64;
         a,b:array[1..1000000]of int64;
    
    Procedure kp(l,r:int64);
    Var
         i,j,t,mid:int64;
    Begin
         i:=l; j:=r; mid:=b[(i+j) div 2];
         repeat
              while b[i]>mid do inc(i);
              while b[j]<mid do dec(j);
              if i<=j then
              begin
                   t:=b[i]; b[i]:=b[j]; b[j]:=t;
                   t:=a[i]; a[i]:=a[j]; a[j]:=t;
                   inc(i); dec(j);
              end;
         until i>j;
         if i<r then kp(i,r);
         if l<j then kp(l,j);
    End;
    
    Begin
         readln(n);
         for i:=1 to n-1 do
              read(a[i]);
         readln(a[n]);
         for i:=1 to n-1 do
              read(b[i]);
         readln(b[n]);
         max:=-1;
         for i:=1 to n do
              if max<a[i]*2+b[i] then
              begin
                   j:=i;
                   max:=a[i]*2+b[i];
              end;
         b[j]:=0;
         writeln(max);
         num:=max-a[j]*2;
         kp(1,n);
         i:=0;
         while i<n-1 do
         begin
              inc(i);
              num:=num+b[i];
              if num+a[i]*2>max+b[i] then
                   max:=num+a[i]*2
              else
                   if num+a[i]*2<=max+b[i] then
                        max:=max+b[i];
              writeln(max);
         end;
         readln;
    End.
    
    

    不科学啊。。这个放到洛谷是全对的啊、
    #1
    AC
    0ms/9269kB

    #2
    AC
    52ms/9269kB

    #3
    AC
    0ms/9269kB

    #4
    AC
    0ms/9269kB

    #5
    AC
    0ms/9269kB

    #6
    AC
    0ms/9269kB

    #7
    AC
    0ms/9269kB
    #8
    AC
    55ms/9269kB

    #9
    AC
    51ms/9269kB

    #10
    AC
    61ms/9269kB
    在这里就不对。。。。vijos测试数据有问题》???

  • 0
    @ 2016-12-21 22:02:12

    var a,s,p,sum,b,c,m1,m2,f:array[0..100000] of longint;
    n,i,j:longint;
    function max(x,y:longint):longint;
    begin
    if x>y then exit(x) else exit(y);
    end;
    procedure qsort(l,r:longint);
    var i,j,k,t,t1,t2:longint;
    begin
    i:=l; j:=r; k:=(i+j) div 2;
    t:=a[k]; a[k]:=a[i];
    t1:=p[k]; p[k]:=p[i];
    while i<j do
    begin
    while (i<j)and(a[j]<t) do dec(j);
    if i<j then
    begin
    a[i]:=a[j];
    p[i]:=p[j];
    inc(i);
    end;
    while (i<j)and(a[i]>t) do inc(i);
    if i<j then
    begin
    a[j]:=a[i];
    p[j]:=p[i];
    dec(j);
    end;
    end;
    p[i]:=t1;
    if i-1>l then qsort(l,i-1);
    if i+1<r then qsort(i+1,r);
    end;
    begin
    assign(input,'salesman.in');
    assign(output,'salesman.out');
    reset(input);
    rewrite(output);
    readln(n);
    for i:=1 to n do read(s[i]);
    readln;
    for i:=1 to n do
    begin
    read(a[i]);
    p[i]:=i;
    end;
    b:=a;
    qsort(1,n);
    a:=b;
    sum[1]:=a[p[1]];
    m1[1]:=p[1];
    for i:=2 to n do
    begin
    sum[i]:=sum[i-1]+a[p[i]];
    if s[m1[i-1]]>s[p[i]] then m1[i]:=m1[i-1]
    else m1[i]:=p[i];
    end;
    m2[n]:=p[n];
    for i:=n-1 downto 1 do
    begin
    if 2*s[m2[i+1]]+a[m2[i+1]]>2*s[p[i]]+a[p[i]] then m2[i]:=m2[i+1]
    else m2[i]:=p[i];
    end;
    for i:=1 to n do
    writeln(max(sum[i-1]+a[m2[i]]+max(s[m1[i-1]],s[m2[i]])*2,sum[i]+s[m1[i]]*2));
    close(input);
    close(output);
    end.

  • 0
    @ 2016-11-18 18:54:04

    贪心
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct data{
    long long dis;
    long long tired;
    };
    data info[100010];
    long long g[100010]={0},h[100010]={0},x[100010]={0},f[100010]={0};
    bool cmp(data a,data b){
    return a.tired<b.tired;
    }
    int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&info[i].dis);
    for(int i=1;i<=n;i++) scanf("%d",&info[i].tired);
    sort(info,info+n+1,cmp);
    for(int i=1;i<=n;i++) g[i]=max(info[i].dis*2+info[i].tired,g[i-1]);
    h[n]=2*info[n].dis;
    for(int i=n;i>=1;i--) h[i]=max(h[i+1],info[i].dis*2);
    for(int i=n;i>=1;i--) x[i]=x[i+1]+info[i].tired;
    for(int i=n;i>=1;i--){
    f[i]=x[i]+h[i];
    f[i]=max(f[i],x[i+1]+g[i-1]);
    }
    for(int i=n;i>=1;i--) printf("%d\n",f[i]);
    return 0;
    }

  • 0
    @ 2016-11-14 12:31:28

    树状数组?

  • 0
    @ 2016-11-03 20:05:17

    http://blog.csdn.net/u013598409/article/details/53025285
    这道题的正解是堆。
    膜拜yww大神。
    ```c++
    #include <cstdio>
    #include <cctype>
    #include <queue>
    using namespace std;

    #define rep(i,a,b) for (int i=(a);i<=(b);i++)

    #define x first
    #define y second
    #define mp make_pair

    typedef pair<int,int> PII;

    const int N=131072;

    int n;
    int s[N],a[N];

    int cur,vis[N];
    priority_queue<PII> qs,qb;
    int res;

    inline int rd(void)
    {
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
    }

    int main(void)
    {
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);

    n=rd();
    rep(i,1,n) s[i]=rd();
    rep(i,1,n) a[i]=rd();

    rep(i,1,n)
    qb.push(mp(2*s[i]+a[i],i));

    PII t1,t2; int e1,e2,cs;
    rep(i,1,n)
    {
    while (!qs.empty())
    {
    t1=qs.top();
    if (vis[t1.y])
    qs.pop();
    else break;
    }
    while (!qb.empty())
    {
    t2=qb.top();
    if (t2.y<cur||vis[t2.y])
    qb.pop();
    else break;
    }

    e1=(!qs.empty());
    e2=(!qb.empty());
    if (!e1&&e2)
    cs=2;
    else if (e1&&!e2)
    cs=1;
    else if (e1&&e2)
    {
    t1=qs.top(),t2=qb.top();
    if (t2.x-2*s[cur]>=t1.x)
    cs=2;
    else cs=1;
    }

    if (cs==1)
    {
    t1=qs.top(); qs.pop();
    vis[t1.y]=1;
    res+=t1.x;
    }
    else if (cs==2)
    {
    t2=qb.top(); qb.pop();
    vis[t2.y]=1;
    rep(j,cur+1,t2.y)
    if (!vis[j])
    qs.push(mp(a[j],j));
    res+=(t2.x-2*s[cur]);
    cur=t2.y;
    }

    printf("%d\n",res);
    }

    return 0;
    }
    ```

  • 0
    @ 2016-10-14 21:05:27

    单调队列+优先队列

  • 0
    @ 2016-10-06 07:50:48

    只需要两个堆

    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<ctime>
    #include<queue>
    using namespace std;
    typedef long long ll;
    int s[100010];
    int a[100010];
    int b[100010];
    typedef pair<int,int> pa;
    priority_queue<pa> q1,q2;
    int main()
    {
    memset(b,0,sizeof(b));
    int n;
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&s[i]);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    int x=0;
    for(i=1;i<=n;i++)
    q2.push(make_pair(a[i]+2*s[i],i));
    int ans=0;
    for(i=1;i<=n;i++)
    {
    while(!q1.empty()&&b[q1.top().second])
    q1.pop();
    while(!q2.empty()&&(b[q2.top().second]||q2.top().second<=x))
    q2.pop();
    int t1=-1,t2=-1;
    if(!q1.empty())
    t1=q1.top().first;
    if(!q2.empty())
    t2=q2.top().first-2*s[x];
    if(t1>t2)
    {
    b[q1.top().second]=1;
    ans+=t1;
    q1.pop();
    }
    else
    {
    b[q2.top().second]=1;
    ans+=t2;
    while(x<q2.top().second)
    {
    x++;
    q1.push(make_pair(a[x],x));
    }
    q2.pop();
    }
    printf("%d\n",ans);
    }
    return 0;
    }

  • 0
    @ 2016-08-06 10:53:10

    不错的好题!
    用构造反证法可以证明,每一次最大都是在前一次基础上增加一个;或者说,每一次最大都是在后一次基础上减少一个。不难发现后一种思路适合使用线段树求解。
    一个棘手的问题是:**如果改变的是最远点,走路疲劳会减少**。不妨增加一个特判,每次把最远的点和次远的点找到,把最远点的疲劳度加上最远点到次远点距离的二倍作为增量。
    那么问题就转化为如何找到最远点和次远点。不难发现最远点和次远点都是单调的,因此可以用摊还O(1)的时间找到他们。这样问题就解决了。总的时间复杂度为O(nlgn+n)=O(nlgn)。
    - 测试数据 #0: Accepted, time = 0 ms, mem = 9164 KiB, score = 10
    - 测试数据 #1: Accepted, time = 0 ms, mem = 9164 KiB, score = 10
    - 测试数据 #2: Accepted, time = 15 ms, mem = 9164 KiB, score = 10
    - 测试数据 #3: Accepted, time = 0 ms, mem = 9160 KiB, score = 10
    - 测试数据 #4: Accepted, time = 0 ms, mem = 9164 KiB, score = 10
    - 测试数据 #5: Accepted, time = 15 ms, mem = 9164 KiB, score = 10
    - 测试数据 #6: Accepted, time = 125 ms, mem = 9164 KiB, score = 10
    - 测试数据 #7: Accepted, time = 93 ms, mem = 9164 KiB, score = 10
    - 测试数据 #8: Accepted, time = 125 ms, mem = 9164 KiB, score = 10
    - 测试数据 #9: Accepted, time = 125 ms, mem = 9168 KiB, score = 10

    Accepted, time = 498 ms, mem = 9168 KiB, score = 100
    ```c++
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;

    class zkw {
    long long arr[400005], max_pos[400005];
    int n;
    public:
    zkw()
    {
    memset(arr, 127, sizeof arr);
    n = 1<<17;
    for (int i = n; i < n+n; i++)
    max_pos[i] = i-n+1;
    }
    inline int pos(int i)
    {
    return i + n - 1;
    }
    inline void fix(int i)
    {
    arr[i] = min(arr[i<<1], arr[(i<<1)+1]);
    max_pos[i] = arr[i] == arr[i<<1] ? max_pos[i<<1] : max_pos[(i<<1)+1];
    if (i > 1)
    fix(i >> 1);
    }
    inline void modify(int i, int j)
    {
    int t = pos(i);
    arr[t] = j;
    fix(t >> 1);
    }
    inline long long top()
    {
    return arr[1];
    }
    inline int top_pos()
    {
    return max_pos[1];
    }
    inline long long in(int i)
    {
    return arr[pos(i)];
    }
    }zkwheap;

    long long n;
    long long len[100005], A[100005];
    long long ans[100005];
    int main()
    {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    scanf("%d", &len[i]);
    A[0] = 0;
    for (int i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
    zkwheap.modify(i, A[i]);
    A[i] += A[i-1];
    }
    ans[n] = A[n]+len[n]+len[n];
    int first = n, second = n-1;
    zkwheap.modify(n, zkwheap.in(n)+2*(len[n]-len[n-1]));
    for (int i = n-1; i >= 1; i--) {
    int tp = zkwheap.top_pos();
    long long val = zkwheap.top();
    ans[i] = ans[i+1] - val;
    zkwheap.modify(tp, 1000000000);
    if (second == tp) {
    while (zkwheap.in(second) >= 10000000)
    second--;
    zkwheap.modify(first, A[first]-A[first-1]+2*(len[first]-len[second]));
    }
    if (first == tp) {
    first = second;
    while (first == second || zkwheap.in(second) >= 10000000)
    second--;
    zkwheap.modify(first, zkwheap.in(first)+2*(len[first]-len[second]));
    }
    }
    for (int i = 1; i <= n; i++)
    printf("%d\n", ans[i]);
    return 0;
    }

  • 0
    @ 2016-07-14 08:58:44

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int maxn=100000+2;
    int ss[maxn],aa[maxn];
    bool idx[maxn];
    struct hh{
    int s,h,xu;
    friend bool operator>(hh a,hh b) {if (a.h!=b.h) return a.h<b.h;else return a.s<b.s;}
    hh(int a=0,int b=0,int c=0){s=a;h=b;xu=c;}
    };
    int main(){
    // freopen("salesman.txt","r",stdin);
    // freopen("my.txt","w",stdout);
    memset(idx,0,sizeof(idx));
    int n;
    cin>>n;
    priority_queue<int,vector<int>,less<int > >q1;
    priority_queue<hh,vector<hh>,greater<hh> >q2;
    for(int i=0;i<n;i++) scanf("%d",&ss[i]);
    for(int i=0;i<n;i++){
    scanf("%d",&aa[i]);
    q2.push(hh(ss[i],ss[i]*2+aa[i],i));
    }
    hh q2m=q2.top();q2.pop();
    int m=q2m.h,c=q2m.s,x=q2m.xu,x0=0;idx[x]=1;
    for(int i=0;i<n;i++){
    printf("%d\n",m);
    if(i==n-1) break;
    int q1m=0;q2m.h=0;
    for(int i=x0;i<x;i++) if(!idx[i]) q1.push(aa[i]);
    x0=x+1;q1m=q1.top();
    while(!q2.empty()){
    q2m=q2.top();
    if(q2m.xu>x) break;
    q2.pop();
    }
    q2m.h-=c*2;
    if(q2m.h>q1m) {
    q2.pop();m+=q2m.h;c=q2m.s;x=q2m.xu;idx[x]=1;/*printf("%d->%d**\n",q2m.xu,q2m.h);*/
    }
    else {
    q1.pop();m+=q1m;/*printf("%d->**\n",q1m);*/
    }
    }
    return 0;
    }

  • 0
    @ 2016-07-12 16:07:58

    Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
    Copyright (c) 1993-2015 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    foo.pas(31,26) Warning: Variable "max" does not seem to be initialized
    Linking foo.exe
    51 lines compiled, 0.1 sec, 28240 bytes code, 1268 bytes data
    1 warning(s) issued
    测试数据 #0: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
    测试数据 #1: WrongAnswer, time = 0 ms, mem = 1584 KiB, score = 0
    测试数据 #2: WrongAnswer, time = 0 ms, mem = 1584 KiB, score = 0
    测试数据 #3: WrongAnswer, time = 0 ms, mem = 1584 KiB, score = 0
    测试数据 #4: WrongAnswer, time = 15 ms, mem = 1588 KiB, score = 0
    测试数据 #5: WrongAnswer, time = 0 ms, mem = 1580 KiB, score = 0
    测试数据 #6: WrongAnswer, time = 406 ms, mem = 1584 KiB, score = 0
    测试数据 #7: Accepted, time = 203 ms, mem = 1584 KiB, score = 10
    测试数据 #8: WrongAnswer, time = 250 ms, mem = 1592 KiB, score = 0
    测试数据 #9: WrongAnswer, time = 328 ms, mem = 1580 KiB, score = 0
    WrongAnswer, time = 1202 ms, mem = 1592 KiB, score = 20
    呵呵!在noip标准数据上过的代码~

  • 0
    @ 2016-07-09 13:34:16

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    long long m,q[100011],w[100011],a[100011],l,s,ans;
    long long cut()
    {
    int m=a[1],x=1,y=2;
    a[1]=a[s];
    s--;
    while(y<=s&&(a[x]<a[y]||a[x]<a[y+1]))
    {
    if(y<s&&a[y]<a[y+1])y++;
    int t=a[x];
    a[x]=a[y];
    a[y]=t;
    x=y;
    y=2*y;
    }
    return m;
    }
    void charu(int k)
    {
    int x=k,si=++s;
    while(k>a[si/2]&&si>1)
    {
    a[si]=a[si/2];
    si/=2;
    }
    a[si]=x;
    }
    int main()
    {
    scanf("%lld",&m);
    for(int i=1;i<=m;i++)
    scanf("%lld",&q[i]);
    for(int i=1;i<=m;i++)
    scanf("%lld",&w[i]);
    long long b=0,c=0,xc=-1;
    for(int i=1;i<=m;i++)
    {
    for(int j=l+1;j<=m;j++)
    {
    int k=(q[j]-l)*2+w[j];
    if(k>c){xc=j;c=k;}
    }
    if(c>b)
    {
    ans+=c;
    for(int j=l+1;j<xc;j++)
    charu(w[j]);
    l=xc;
    c=0;
    }
    else
    ans+=b;
    b=cut();
    printf("%lld\n",ans);
    }
    return 0;
    }

  • 0
    @ 2016-06-25 22:01:09

    //刚刚那个不规范 求指点
    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    long zhuhu[100001][2];
    long meigezhuhudezhi[100001], linshizongzhi[100001], jieguo[100001];

    long main(void) {

    long max, i, j;
    scanf("%ld", &max);
    for (i = 0;i < max;i++)
    scanf("%ld", &zhuhu[i][0]);//记录距离
    for (i = 0;i < max;i++)
    scanf("%ld", &zhuhu[i][1]);//记录产品疲劳值
    long dangqianzuileizhuhu = 0;
    for (i = 0;i < max;i++) {
    linshizongzhi[i] = 2 * zhuhu[i][0] + zhuhu[i][1];
    if (linshizongzhi[dangqianzuileizhuhu] < linshizongzhi[i])
    dangqianzuileizhuhu = i;

    }
    jieguo[0] = linshizongzhi[dangqianzuileizhuhu];
    long temp;
    for (i = 0;i < max;i++)
    {
    /* temp = zhuhu[dangqianzuileizhuhu][0] - zhuhu[i][0];
    if (temp < 0)
    linshizongzhi[i]=2*abs(zhuhu[dangqianzuileizhuhu][0] - zhuhu[i][0]);
    else linshizongzhi[i] -= zhuhu[i][0];*/

    if (i < dangqianzuileizhuhu)
    linshizongzhi[i] -= 2 * zhuhu[i][0];
    else
    linshizongzhi[i] += 2 * (zhuhu[i][0] - zhuhu[dangqianzuileizhuhu][0]) - 2 * zhuhu[i][0];
    }
    linshizongzhi[dangqianzuileizhuhu] = 0;
    long l = 1;
    for (i = 0;i < max;i++) {
    temp = 0;
    for (j = 0;j < max;j++)
    if (linshizongzhi[temp] < linshizongzhi[j])
    temp = j;
    jieguo[l] = jieguo[l - 1] + linshizongzhi[temp];
    linshizongzhi[temp] = 0;
    l++;
    }
    for (i = 0;i < max;i++) {
    printf("%ld\n", jieguo[i]);
    }
    // system("pause");
    }

  • 0
    @ 2016-06-25 22:00:25

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    long 住户[100001][2];
    long 每个住户的值[100001], 临时总值[100001], 结果[100001];

    int main(void) {

    long 数量,i,j;
    scanf("%ld", &数量);
    for (i = 0;i < 数量;i++)
    scanf("%ld", &住户[i][0]);//记录距离
    for (i = 0;i < 数量;i++)
    scanf("%ld", &住户[i][1]);//记录产品疲劳值
    long 临时最大,当前最累住户=0;
    for (i = 0;i < 数量;i++) {
    临时总值[i] = 2*住户[i][0] + 住户[i][1];
    if (临时总值[当前最累住户] < 临时总值[i])
    当前最累住户 = i;

    }
    结果[0] = 临时总值[当前最累住户];
    long temp;
    for (i = 0;i < 数量;i++)
    {
    /* temp = 住户[当前最累住户][0] - 住户[i][0];
    if (temp < 0)
    临时总值[i]=2*abs(住户[当前最累住户][0] - 住户[i][0]);
    else 临时总值[i] -= 住户[i][0];*/

    if (i < 当前最累住户)
    临时总值[i] -= 2 * 住户[i][0];
    else
    临时总值[i] += 2 * (住户[i][0] - 住户[当前最累住户][0])-2*住户[i][0];
    }
    临时总值[当前最累住户] = 0;
    long l=1;
    for (i = 0;i < 数量;i++) {
    temp = 0;
    for (j = 0;j < 数量;j++)
    if (临时总值[temp] < 临时总值[j])
    temp =j;
    结果[l] = 结果[l - 1]+临时总值[temp];
    临时总值[temp] = 0;
    l++;
    }
    for (i = 0;i < 数量;i++) {
    printf("%ld\n", 结果[i]);
    }
    return 0;
    // system("pause");
    } //为什么ac不了 我这里有的数据都通过了

    • @ 2016-09-06 23:22:27

      第一次看到用中文定义变量,吓得我虎躯一震……

  • 0
    @ 2016-05-28 17:27:44
    #include<cstdio>
    #include<queue>
    using namespace std;
    int s[100100],a[100100];
    int Next[100100],Last,Now;
    int n,t,sum;
    priority_queue<int>Q;
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&s[i]);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        Next[n+1]=n+1;
        s[n+1]=a[n+1]=0;
        for(int i=n;i>=1;i--)
        {
            t=Next[i+1];
            if(a[i]+s[i]*2>a[t]+s[t]*2)
                Next[i]=i;
            else Next[i]=t;
        }
        sum=0;
        Last=Now=0;
        for(int k=1;k<=n;k++)
        {
            Last=Now;
            t=Next[Last+1];
            if(Q.empty()||Q.top()+s[Last]*2<a[t]+s[t]*2)
            {
                sum+=a[t];
                printf("%d\n",sum+s[t]*2);
                Now=t;
            }
            else
            {
                sum+=Q.top();
                Q.pop();
                printf("%d\n",sum+s[Last]*2);
            }
            for(int i=Last+1;i<Now;i++)
                Q.push(a[i]);
        }
        return 0;
    }
    
  • 0
    @ 2016-05-26 13:12:16

    看见楼下是每次都暴力找的最大值,如果第一次最大值在1,第二次在2,第三次在3…这种情况下楼下的做法就退化到N^2了……可能是数据比较弱了吧(不过官方数据更弱)
    所以我的思路和楼下差不多,不过用了线段树求最大值,严格的N log N。
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <queue>
    #include <algorithm>
    using namespace std;

    int t[262145],tag[262145],S,n,pos;
    int s[100010],a[100010];
    priority_queue<int>Q;
    void build() {
    for (S=1;S<=n+1;S<<=1);
    for (int i=1;i<=n;i++) {
    t[S+i]=s[i]+a[i];
    tag[S+i]=i;
    }
    for (int i=S-1;i>0;i--) {
    if (t[i<<1]>=t[(i<<1)+1]) {
    tag[i]=tag[i<<1];
    t[i]=t[i<<1];
    }
    else {
    tag[i]=tag[(i<<1)+1];
    t[i]=t[(i<<1)+1];
    }
    }
    return;
    }
    int query(int l) {
    int ans=-1,r=S+n+1;
    for (l+=S;l^r^1;l>>=1,r>>=1) {
    if ((l&1)^1 && ans<t[l^1]) {
    ans=t[l^1];
    pos=tag[l^1];
    }
    if (r&1 && ans<t[r^1]) {
    ans=t[r^1];
    pos=tag[r^1];
    }
    }
    return ans;
    }
    int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
    scanf("%d",s+i);
    s[i]<<=1;
    }
    for (int i=1;i<=n;i++) {
    scanf("%d",a+i);
    }
    build();
    int now=0,total=0;
    for (int num=1,ans,re;num<=n;num++) {
    ans=-1;
    if (!Q.empty())
    ans=Q.top();
    re=query(now)-s[now];
    if (re>ans) {
    total+=re;
    for (int i=now+1;i<pos;i++) {
    Q.push(a[i]);
    }
    now=pos;
    }
    else {
    total+=Q.top();
    Q.pop();
    }
    printf("%d\n",total);
    }
    return 0;
    }

信息

ID
1977
难度
8
分类
(无)
标签
递交数
2212
已通过
253
通过率
11%
上传者