题解

13 条题解

  • 2
    @ 2017-09-18 10:49:26

    短且简
    贪心 是基本思想。
    其他操作主要体现在 前缀 来优化上。

    这里推荐一个博主的写法,先看为敬。

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    struct SEGMENT {
        int l, r, v, maxv, p;
    };
    int N, M, K, Ans;
    // Arr是到达时间, Sat是出发时间
    int Arr[1005], Sat[1005], Out[1005], Man[1005], D[1005];
    int main () {
        
        ios::sync_with_stdio(false);
        cin >> N >> M >> K;
        for(int i=1; i<N; i++) cin >> D[i];
        for(int i=1, t, a, b; i<=M; i++) {
            cin >> t >> a >> b;
            // 先减去每个人 "上车前的时间" ,后面直接用 "到达时间*到达人数" 整体计算消耗时间,从而优化程序 
            Ans-=t;
            Out[b]++;
            Sat[a]=max(Sat[a], t);
        }
        while(K--) {        
            memset(Man, 0, sizeof(Man));    
            for(int i=1; i<=N; i++) Arr[i]=max(Arr[i-1], Sat[i-1])+D[i-1]; 
            // 从 "后缀" 开始寻找当前路径上正在运输的人数
            for(int i=N; i>1; i--) {
                if (D[i-1]) {
                    Man[i-1]=Out[i];
                    if (Arr[i]>Sat[i]) Man[i-1]+=Man[i];    
                } 
                else Man[i-1]=0;
            }
            int maxm=0, p=0;
            for(int i=1; i<=N; i++) 
                if (Man[i]>maxm) {
                    maxm=Man[i];
                    p=i;      
                }
            if (!p) break;
            D[p]--;    
        }
        for(int i=1; i<=N; i++) Arr[i]=max(Arr[i-1], Sat[i-1])+D[i-1];
        for(int i=1; i<=N; i++) Ans+=Arr[i]*Out[i];
        cout << Ans;
        return 0;
        
    }
    
    • @ 2017-10-24 21:03:34

      你这个code为什么必须要

      for(int i=1; i<=N; i++) 
                  if (Man[i]>maxm) {
                      maxm=Man[i];
                      p=i;      
                  }
      

      来求到第一个i使得人数最多呢
      我改成只要==maxm就更新i 就挂了 必须找第一个这样的点 为什么呢

  • 1
    @ 2021-09-04 17:02:40
    #include <bits/stdc++.h>
    using namespace std;
    
    const int N=1010;
    const int M=10010;
    int d[N],getto[N],getoff[N],latest[N], f[N];
    struct Passenger{
        int t,s,e;
    }a[M];
    
    inline int read()
    {
        char ch=getchar();
        int x=0;
        while(!isdigit(ch))
            ch=getchar();
        while(isdigit(ch)){
            x=x*10+ch-'0';
            ch=getchar();
        }
        return x;
    }
    
    int main()
    {
        int n,m,k;
        n=read();
        m=read();
        k=read();
        for(int i=1; i<n; i ++)
            d[i] = read();
        for(int i=1; i<=m; i ++){
            a[i].t=read();
            a[i].s=read();
            a[i].e=read();
            latest[a[i].s]=max(latest[a[i].s], a[i].t);
            getoff[a[i].e]++;
        }
        for(int i=1; i<=n; i ++)
            getto[i]=max(getto[i-1],latest[i-1])+d[i-1];
        while(k--){
            for(int i=n; i>=2; i--){
                if(!d[i-1])
                    f[i-1]=0;
                else{
                    f[i-1]=getoff[i];
                    if(getto[i]>latest[i])
                        f[i-1]=f[i-1]+f[i];
                }
            }
            int maxtime=0, pos=0;
            for (int i=1; i<n; i ++)
                if (f[i]>maxtime){
                    maxtime=f[i];
                    pos=i;
                }
            if(pos==0)
                break;
            d[pos]--;
            for(int i=pos+1; i<=n; i++)
                getto[i]=max(getto[i-1],latest[i-1])+d[i-1];
        }
        int tot=0;
        for(int i=1; i<=m; i++)
            tot+=getto[a[i].e]-a[i].t;
        cout<<tot;
        return 0;
    }
    
  • 1
    @ 2016-08-07 11:32:59
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    int n,m,k,ans=0;
    int D[1005],T[10005],qi[10005],zhong[10005];
    int late[1005],ari[1005],sum[1005],maxn[1005];
    int up[1005],down[1005];
    int main(){
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<n;i++) 
           scanf("%d",&D[i]);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&T[i],&qi[i],&zhong[i]);
            maxn[qi[i]]=max(maxn[qi[i]],T[i]);//人最晚到达某个景点的时间 ; 
            up[qi[i]]++;//上车的人数 ; 
            down[zhong[i]]++;//下车的人数; 
        }
        for(int i=1;i<=n;i++){
            ari[i]=late[i-1]+D[i-1];//车到达每个景点的时间; 
            late[i]=max(ari[i],maxn[i]);//最后一个到达这个景点的时间 
            sum[i]=down[i+1];//要下车的人数; 
        }
        for(int i=1;i<=m;i++)
            ans+=(ari[zhong[i]]-T[i]);//不使用加速器花费的总时间; 
        for(int i=n-2;i>=1;i--)
            if(ari[i+1]>maxn[i+1]) 
              sum[i]+=sum[i+1];//找最大的 人等车的区间的 下车的人数; 
        while(k>0){
            int x=0;
            for(int i=1;i<n;i++)
                if(sum[i]>sum[x]&&D[i]>0) 
                  x=i;//找下车人数最多的区间,(加速的效果最好) 
            if(x==0) break;
                D[x]--;//两个景点间的时间——; 
                k--;//加速装置的个数——; 
                ans-=sum[x];//减去节省的时间;(有几个要下车人就节省几分钟); 
            for(int j=x;j<=n;j++){
                ari[j]=late[j-1]+D[j-1];
                late[j]=max(ari[j],maxn[j]);
                sum[j]=down[j+1];
            }
            for(int j=n-2;j>=x;j--)
                if(ari[j+1]>maxn[j+1]) 
                  sum[j]+=sum[j+1];//用完一个加速装置后重新统计区间; 
        }
        printf("%d",ans);
        return 0; 
    }
    
  • 0
    @ 2017-11-02 13:28:53

    先把不加速的总时间算出来(有10分。。)
    然后计算加速器的最大影响(影响加速的时间段和使所有乘客不用等待)

  • 0
    @ 2014-10-29 20:34:42

    #include<stdio.h>
    #include<stdlib.h>
    int max(int a,int b)
    {
    if(a>b) return a;
    else return b;
    }
    int main()
    {
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int i,d[1001]={0};
    for(i=1;i<=n-1;i++) scanf("%d",&d[i]);
    int t[10001],a[10001],b[10001];
    int people[1001]={0},go[1001]={0},arrive[1001]={0};
    //people[i]为在第i个站用1个加速器能造福的人数即1个加速器的效益;
    //go[i]为第i站的出发时间;arrive[i]为第i站的到达时间;
    for(i=1;i<=m;i++)
    {
    scanf("%d%d%d",&t[i],&a[i],&b[i]);
    people[b[i]-1]++;
    go[a[i]]=max(go[a[i]],t[i]);
    }
    for(i=2;i<=n;i++)
    arrive[i]=max(arrive[i-1],go[i-1])+d[i-1];
    int j;
    while(k--)//每次循环找出这个加速器用在哪一站的效益最大;
    {
    int max1=0,c=0,T=0;
    for(j=n;j>1;j--)//从后往前推,则直到不符合要求(第j站)的下一站(第j+1站)所得的效益才是在第j+1站用加速器得到的效益;(如果j和j+1都符合要求,则第j站的效益肯定大于第j+1站,所以要从后往前推);
    {
    if(arrive[j]<=go[j]) c=0;//如果到达时间小于出发时间,用加速器也没有效益;
    c+=people[j-1];//反之,记录下这个加速器的效益;
    if(d[j-1]>0&&c>max1) max1=c,T=j-1;
    }
    if(T==0) break;
    d[T]--;
    for(i=T+1;i<=n;i++) arrive[i]=max(arrive[i-1],go[i-1])+d[i-1];//每用一次加速器则更新所用加速器的那站之后的站的到达时间;
    }
    int sum=0;
    for(i=1;i<=n;i++)

    arrive[i]=max(arrive[i-1],go[i-1])+d[i-1];//最后再更新一次,以免有漏更新的站;
    for(i=1;i<=m;i++)
    sum+=arrive[b[i]]-t[i];
    printf("%d",sum);
    fclose(stdin);
    fclose(stdout);
    return 0;
    }

  • 0
    @ 2014-07-31 14:09:20

    #include <cstdio>
    #include <iostream>
    using namespace std;
    int dis[1003],Time[1003],tn[1003],Up[1003],Down[1003];
    bool picked[1003];
    int ans,n,m,k,kans;
    int main()
    {
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<n;i++) scanf("%d",dis+i);
    for (int i=1,t,l,r;i<=m;i++)
    {
    scanf("%d%d%d",&t,&l,&r);
    Up[l]++,Down[r]++;
    Time[l]=max(t,Time[l]);
    kans+=t;
    }
    for (int i=1;i<=n;i++)
    tn[i]=max(tn[i-1],Time[i-1])+dis[i-1];
    while (k--)
    {
    int M_cng=0,C_Cng=0,T=0;
    for (int j=n;j>1;j--)
    {
    if (tn[j]<=Time[j]) C_Cng=0;
    C_Cng+=Down[j];
    if (dis[j-1] && C_Cng>M_cng) M_cng=C_Cng,T=j-1;
    }
    if (!T) break;
    dis[T]--;
    for (int i=T+1;i<=n;i++) tn[i]=max(tn[i-1],Time[i-1])+dis[i-1];
    }
    ans=0;
    for (int i=1;i<=n;i++)
    tn[i]=max(tn[i-1],Time[i-1])+dis[i-1],ans+=Down[i]*tn[i];
    printf("%d\n",ans-kans);
    return 0;
    }

  • -2
    @ 2016-09-14 21:48:28

    11年的题怎么都这么水。。。
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;

    const int maxn = 1000 + 10;
    const int maxm = 10000 + 10;

    int n, m, k;
    int ans;
    int D[maxn], wait[maxn], down[maxn];
    int arrive[maxn], leave[maxn], sum[maxn];
    int T[maxm], A[maxm], B[maxm];

    int main ()
    {
    // freopen("in.txt", "r", stdin);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) cin >> D[i];
    for (int i = 0; i < m; i++) {
    cin >> T[i] >> A[i] >> B[i];
    wait[A[i]] = max(wait[A[i]], T[i]);
    down[B[i]]++;
    }

    for (int i = 1; i <= n; i++) {
    arrive[i] = leave[i-1] + D[i-1];
    leave[i] = max(arrive[i], wait[i]);
    sum[i] = down[i+1];
    }

    for (int i = 0; i < m; i++)
    ans += arrive[B[i]] - T[i];

    for (int i = n-2; i >= 1; i--)
    if (arrive[i+1] > wait[i+1]) sum[i] += sum[i+1];

    while (k) {
    int cur = 0;
    for (int i = 1; i < n; i++)
    if (sum[i] > sum[cur] && D[i]) cur = i;

    if (!cur) break;
    D[cur]--; k--;
    ans -= sum[cur];

    for (int i = cur; i <= n; i++) {
    arrive[i] = leave[i-1] + D[i-1];
    leave[i] = max(arrive[i], wait[i]);
    sum[i] = down[i+1];
    }

    for (int i = n-2; i >= cur; i--)
    if (arrive[i+1] > wait[i+1]) sum[i] += sum[i+1];
    }
    cout << ans;
    return 0;
    }
    ```

  • -2
    @ 2015-10-07 15:03:16

    http://www.ofsxb.com/archives/128
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    int n,m,k;
    int D[1000+10],T[10000+10],A[10000+10],B[10000+10];

    int ans=0;
    int s[1000+10],t[1000+10],sum[1000+10],M[1000+10];
    int up[1000+10],down[1000+10];

    int dd[1000+10];
    int main()
    {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<n;i++) scanf("%d",&D[i]);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&T[i],&A[i],&B[i]),M[A[i]]=max(M[A[i]],T[i]),up[A[i]]++,down[B[i]]++;

    for(int i=1;i<=n;i++)
    {
    t[i]=s[i-1]+D[i-1];
    s[i]=max(t[i],M[i]);
    sum[i]=down[i+1];
    }
    for(int i=1;i<=m;i++)
    ans+=(t[B[i]]-T[i]);

    for(int i=n-2;i>=1;i--)
    if(t[i+1]>M[i+1]) sum[i]+=sum[i+1];

    while(k>0)
    {
    int x=0;
    for(int i=1;i<n;i++)
    if(sum[i]>sum[x]&&D[i]>0) x=i;

    if(x==0) break;

    D[x]--;
    k--;
    ans-=sum[x];

    for(int j=x;j<=n;j++)
    {
    t[j]=s[j-1]+D[j-1];
    s[j]=max(t[j],M[j]);
    sum[j]=down[j+1];
    }

    for(int j=n-2;j>=x;j--)
    if(t[j+1]>M[j+1]) sum[j]+=sum[j+1];
    }
    cout<<ans;

    return 0;
    }

  • -2
    @ 2015-10-04 14:34:56

    /*

    Author : Slience_K
    Belong : C++
    Pro : NOIP 2011 - 2 - 3

    */

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int n , m , k , d[ 1005 ];
    int st[ 1005 ] , down[ 1005 ] , art[ 1005 ] , ans , sum[ 1005 ];
    int main(){
    scanf( "%d%d%d" , &n , &m , &k );
    for( int i = 2 ; i <= n ; i++ )
    scanf( "%d" , &d[ i ] );
    ans = 0;
    for( int i = 1 , a , b , c ; i <= m ; i++ ){
    scanf( "%d%d%d" , &a , &b , &c );
    down[ c ]++;
    ans -= a;
    st[ b ] = max( st[ b ] , a );
    }
    for( int i = 2 ; i <= n ; i++ )
    art[ i ] = max( art[ i - 1 ] , st[ i - 1 ] ) + d[ i ];
    for( int l = 1 ; l <= k ; l++ ){
    for( int i = n ; i >= 2 ; i-- ){
    sum[ i ] = down[ i ];
    if ( art[ i ] > st[ i ] ) sum[ i ] += sum[ i + 1 ];
    }
    int maxn = 0 , pos = 0;
    for( int i = 2 ; i <= n ; i++ )
    if (( maxn < sum[ i ] )&&( d[ i ] >= 1 )){
    maxn = sum[ i ];
    pos = i;
    }
    if ( !pos ) break;
    d[ pos ] -= 1;
    for( int i = pos ; i <= n ; i++ )
    art[ i ] = max( st[ i - 1 ] , art[ i - 1 ] ) + d[ i ];
    }
    for( int i = 1 ; i <= n ; i++ )
    ans += down[ i ] * art[ i ];
    printf( "%d" , ans );
    return 0;
    }

  • -2
    @ 2014-10-28 16:39:29

    NOIP2014赛前AC留念
    (如此捉鸡的贪心我也是醉了……)
    var ans,n,m,k,i:longint;
    arrive,d,t,a,b,down,latest:array[0..10001] of longint;

    function mmax(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;

    procedure doit;
    var i,j,max,tip,pos:longint;
    begin
    pos:=0;
    max:=0;
    for i:=1 to n-1 do
    if d[i]>0 then
    begin
    tip:=0;
    for j:=i+1 to n do
    begin
    tip:=tip+down[j];
    if arrive[j]<=latest[j] then break;
    end;

    if tip>max then
    begin
    max:=tip;
    pos:=i;
    end;
    end;
    dec(d[pos]);
    for i:=2 to n do
    arrive[i]:=mmax(arrive[i-1],latest[i-1])+d[i-1];
    dec(k);
    end;

    begin
    //assign(input,'t6.in');
    //assign(output,'t6.out');
    //reset(input);
    //rewrite(output);
    readln(n,m,k);
    for i:=1 to n-1 do read(d[i]);
    for i:=1 to m do
    begin
    readln(t[i],a[i],b[i]);
    if latest[a[i]]<t[i] then latest[a[i]]:=t[i];
    inc(down[b[i]]);
    end;
    arrive[1]:=latest[1];
    for i:=2 to n do
    arrive[i]:=mmax(arrive[i-1],latest[i-1])+d[i-1];
    while k>0 do doit;

    for i:=2 to n do
    arrive[i]:=mmax(arrive[i-1],latest[i-1])+d[i-1];
    ans:=0;
    for i:=1 to m do
    ans:=ans+arrive[b[i]]-t[i];
    writeln(ans);
    //close(input);
    //close(output);
    end.

    • @ 2014-10-28 16:41:37

      要记住每个旅客的旅行时间只与他的下车时间有关!!!
      每次都找到影响最多旅客下车时间的那段路。

  • -2
    @ 2013-08-30 22:53:58

    var
    n,m,k,i,j,a,b,c,cct,ans,max1:longint;
    time,last,d,data,num:array[0..2000] of longint;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;
    begin
    readln(n,m,k);
    for i:=2 to n do read(d[i]);
    for i:=1 to m do
    begin
    readln(a,b,c);
    ans:=ans-a;
    inc(num[c]);
    last[b]:=max(last[b],a);
    end;
    for i:=2 to n do time[i]:=max(time[i-1],last[i-1])+d[i];
    for i:=1 to k do
    begin
    for j:=n downto 2 do
    begin
    data[j]:=num[j];
    if last[j]<time[j] then data[j]:=data[j]+data[j+1];
    end;
    max1:=0;
    for j:=2 to n do
    if (data[j]>max1) and (d[j]>0) then
    begin
    max1:=data[j];
    cct:=j;
    end;
    dec(d[cct]);
    for j:=cct to n do
    time[j]:=max(time[j-1],last[j-1])+d[j];
    end;
    for i:=2 to n do
    ans:=ans+num[i]*time[i];
    writeln(ans);
    end.

  • -2
    @ 2012-10-19 23:23:00

    VijosNT Mini 2.0.5.7 Special for Vijos

    编译通过...

    ├ 测试数据 01:答案正确... (0ms, 676KB)

    ├ 测试数据 02:答案正确... (0ms, 676KB)

    ├ 测试数据 03:答案正确... (0ms, 676KB)

    ├ 测试数据 04:答案正确... (0ms, 676KB)

    ├ 测试数据 05:答案正确... (0ms, 676KB)

    ├ 测试数据 06:答案正确... (0ms, 676KB)

    ├ 测试数据 07:答案正确... (0ms, 676KB)

    ├ 测试数据 08:答案正确... (0ms, 676KB)

    ├ 测试数据 09:答案正确... (0ms, 676KB)

    ├ 测试数据 10:答案正确... (0ms, 676KB)

    ├ 测试数据 11:答案正确... (0ms, 676KB)

    ├ 测试数据 12:答案正确... (0ms, 676KB)

    ├ 测试数据 13:答案正确... (0ms, 676KB)

    ├ 测试数据 14:答案正确... (0ms, 676KB)

    ├ 测试数据 15:答案正确... (0ms, 676KB)

    ├ 测试数据 16:答案正确... (0ms, 676KB)

    ├ 测试数据 17:答案正确... (0ms, 676KB)

    ├ 测试数据 18:答案正确... (0ms, 676KB)

    ├ 测试数据 19:答案正确... (0ms, 676KB)

    ├ 测试数据 20:答案正确... (32ms, 676KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 32ms / 676KB

    var

    n,m,k,tt,ans,i,j,t:longint;

    a,b:array[1..10000]of longint;

    sum,time,late,d,f:array[1..1000]of longint;

    function max(x,y:longint):longint;

    begin

    if xlate[a[i]] then late[a[i]]:=t;

    for j:=b[i] to n do inc(sum[j]);

    end;

    end;

    procedure main;

    var i,ma,ii:longint;

    begin

    while k>0 do

    begin

    dec(k);

    for i:=2 to n do time[i]:=max(time,late)+d;

    f[n]:=n;

    for i:=n-1 downto 1 do

    if time0)and(ma

    • @ 2013-08-08 21:58:19

      楼主main函数倒数第9行 f[i]:=f 应该是 f[i]:=f[i+1]

    • @ 2013-08-08 22:06:49

      而且init函数中应该是 for j:=a[i] to b[i] do

    • @ 2013-08-08 22:07:09

      好吧,我不知道我是不是对的

  • -3
    @ 2016-10-12 22:21:24

    要认真审题啊!!!!
    只需每次查找某点从一个此点到后某点间的下车人数最大, 且保证在这两点间车到达每点的时间大于该点最后一个人上车的时间

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n,m,k,D[1005]={0},last[1005]={0},down[1005]={0},s[1005]={0},sum[1005]={0};
    int T[10005],A[10005],B[10005],ari[1005]={0};
    int main(){
    //freopen("bus.in","r",stdin);
    int i,t,a,b,ans=0;
    scanf("%d %d %d",&n,&m,&k);
    for(i=1;i<n;i++) scanf("%d",&D[i]);
    for(i=1;i<=m;i++){
    scanf("%d %d %d",&t,&a,&b);
    T[i]=t;A[i]=a;B[i]=b;
    last[a]=max(last[a],t);
    down[b]++;
    }
    for(i=1;i<=n;i++){
    ari[i]=s[i-1]+D[i-1];
    s[i]=max(ari[i],last[i]);
    sum[i]=down[i+1];
    }
    for(i=1;i<=m;i++){
    ans+=ari[B[i]]-T[i];
    }
    for(i=n-2;i>=1;i--){
    if(ari[i+1]>last[i+1])
    sum[i]+=sum[i+1];
    }
    while(k){
    int x=0;
    for(i=1;i<=n-1;i++)
    if(sum[i]>sum[x]&&D[i]>0) x=i;
    if(x==0) break;
    D[x]--;
    ans-=sum[x];
    k--;
    for(i=x;i<=n;i++){
    ari[i]=s[i-1]+D[i-1];
    s[i]=max(ari[i],last[i]);
    sum[i]=down[i+1];
    }
    for(i=n-2;i>=x;i--){
    if(ari[i+1]>last[i+1])
    sum[i]+=sum[i+1];
    }
    }
    printf("%d\n",ans);
    return 0;
    }

  • 1

信息

ID
1741
难度
5
分类
贪心 | 数据结构 点击显示
标签
递交数
1477
已通过
470
通过率
32%
被复制
10
上传者