1综合强化刷题,贪心算法推导

时间:2019-09-25 09:04来源: 操作系统
题目描述 在一个银行,只有一个营业员。很多人要一起办理业务,每个人需要ai分钟,不过前提是他们都立即办理。事实上,现在必定每个人都会等一段时间。由于业务的特殊性,每个

题目描述

在一个银行,只有一个营业员。很多人要一起办理业务,每个人需要ai分钟,不过前提是他们都立即办理。事实上,现在必定每个人都会等一段时间。由于业务的特殊性,每个人多等一分钟,他最终办事的时间就会多bi分钟。作为志愿者,你的任务就是安排他们的先后顺序,使他们最后的总时间最小。

输入:第一行一个数n,表示有n个人。接下来n行每行两个数ai,bi。

输出:一行一个整数,输出最小时间。答案对1000000009取模。

样例输入

2

1 1

2 2

样例输出

5

提示

若1先,那么代价为1+=5

若2先,那么代价为2+=5

对于10%的数据:1<=n<=10

对于100%数据:1<=n<=10000,0<=ai,bi<=10000

明显的贪心思想。

假设只有两个人:x和y。那么谁应该排在前面呢。(用x.a与x.b来表示x的ai与bi,y同理)

若x先,则时间要用:x.a+x.a*y.b+y.a

若y先,则时间要用:y.a+y.a*x.b+x.a

设第一个时间小于第二个时间:x.a+x.a*y.b+y.a<y.a+y.a*x.b+x.a

左边右边x.a,y.a移项抵消,只剩下:x.a*y.b<y.a*x.b。

则只要满足这条件,x就该排在y前面。就可以用这个条件来进行快排。

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 const int mod=1000000009; 6 struct zhu{ 7     int a,b; 8 }e[10010]; 9 int cmp(zhu x,zhu y)10 {11     return x.a*y.b<y.a*x.b;//用此公式来快排重定义12 }13 int mark[10010];14 int main()15 {16     int n;17     scanf("%d",&n);18     for(int i=1;i<=n;i++)scanf("%d%d",&e[i].a,&e[i].b);19     sort(e+1,e+n+1,cmp);20     long long ans=0;21     for(int i=1;i<=n;i++)22     {23         ans=(ans+ans*e[i].b+e[i].a)%mod;//此时的顺序就是最优顺序,依次加答案即可24     }25     printf("%lld",ans);26 }

通过不等式求出来的贪心是一定正确的

最大值(max)

Time Limit:1000ms   Memory Limit:128MB

 

题目描述

LYK有一本书,上面有很多有趣的OI问题。今天LYK看到了这么一道题目:

这里有一个长度为n的正整数数列ai(下标为1~n)。并且有一个参数k。

你需要找两个正整数x,y,使得x+k<=y,并且y+k-1<=n。并且要求a[x]+a[x+1]+…+a[x+k-1]+a[y]+a[y+1]+…+a[y+k-1]最大。

LYK并不会做,于是它把题扔给了你。

 

输入格式(max.in)

第一行两个数n,k。

    第二行n个数,表示ai。

 

输出格式(max.out)

两个数表示x,y。若有很多种满足要求的答案,输出x最小的值,若x最小仍然还有很多种满足要求的答案,输出y最小的值。 

 

输入样例

5 2

6 1 1 6 2

 

输出样例

1 4

 

对于30%的数据n<=100。

对于60%的数据n<=1000

对于100%的数据1<=n<=100000,1<=k<=n/2,1<=ai<=10^9。

 

 

永利皇宫463娱乐网址 1永利皇宫463娱乐网址 2

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std;
int n,k,x,y;
long long q,sum[N];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int main()
{    
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    n=read(),k=read();
    for(int i=1;i<=n;i++) x=read(),sum[i]=sum[i-1]+(LL)x;
    for(int i=k;i<=n;i++)
      if(q<sum[i]-sum[i-k]) 
      {
          if(y+k<=i-k+1) x=y;
        y=i-k+1,q=sum[i]-sum[i-k];
      }
    printf("%d %d",x,y);
    return 0;
}

20分、、、、(代码出了点小问题)

 

这个题说白了就是让着找最大的k个数的前缀和的位置跟次大的k个数的前缀和的位置,在找这个次大的位置的时候,一定不要忘记x+k<y即我们设最大的数的位置为x,现在我们找到的位置为i,那么这两个位置一定要满足:abs(x-i)>=k,注意我们这个地方找的是次大的,一定不要在找的时候找了两遍最大的

永利皇宫463娱乐网址 3永利皇宫463娱乐网址 4

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std;
int n,k,x,y,a[N];
long long q,sum[N];
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int main()
{
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    n=read(),k=read();
    for(int i=1;i<=n;i++) 
    {
        a[i]=read();
        if(i<=k) sum[i]=sum[i-1]+(LL)a[i];
        else sum[i]=sum[i-1]+(LL)a[i]-(LL)a[i-k];
    }
    for(int i=k;i<=n;i++)
     if(q<sum[i]) q=sum[i],x=i;
    q=0;
    for(int i=k;i<=n;i++)
     if(i!=x&&q<sum[i]&&abs(i-x)>=k) 
       q=sum[i],y=i;
    if(x>y) swap(x,y);
    x=x-k+1,y=y-k+1;
    printf("%d %d",x,y);
    return 0;
}

AC代码

 

 

 

 

 

吃东西(eat)

Time Limit:2000ms   Memory Limit:1024MB

 

题目描述

一个神秘的村庄里有4家美食店。这四家店分别有A,B,C,D种不同的美食。LYK想在每一家店都吃其中一种美食。每种美食需要吃的时间可能是不一样的。

现在给定第1家店A种不同的美食所需要吃的时间a1,a2,…,aA。

    给定第2家店B种不同的美食所需要吃的时间b1,b2,…,bB。

以及c和d。

LYK拥有n个时间,问它有几种吃的方案。

 

输入格式(eat.in)

第一行5个数分别表示n,A,B,C,D。

第二行A个数分别表示ai。

第三行B个数分别表示bi。

第四行C个数分别表示ci。

第五行D个数分别表示di。

 

输出格式(eat.out)

一个数表示答案。

 

输入样例

11 3 1 1 1

4 5 6

3

2

1

 

输出样例

2

 

对于30%的数据A,B,C,D<=50

对于另外30%的数据n<=1000。

对于100%的数据1<=n<=100000000,1<=A,B,C,D<=5000,0<=ai,bi,ci,di<=100000000。

 

永利皇宫463娱乐网址 5永利皇宫463娱乐网址 6

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 10000
using namespace std;
int n,t,ans,sum[5],q[5][N];
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void dfs(int s,int t)
{
    if(t<=0) return ;
    if(s==4+1)
    {
        ans++;
        return ;
    }
    for(int i=1;i<=sum[s];i++) 
     dfs(s+1,t-q[s][i]);
}
int main()
{
    freopen("eat.in","r",stdin);
    freopen("eat.out","w",stdout);
    t=read();
    for(int i=1;i<=4;i++) sum[i]=read();
    for(int i=1;i<=4;i++) 
     for(int j=1;j<=sum[i];j++) 
       q[i][j]=read();
    dfs(1,t);
    printf("%d",ans);
    return 0;
}

30分的暴力搜索

 

永利皇宫463娱乐网址,我们将4家店分成两部分,第一部分为只在A和B吃一样东西耗费的时间,另一部分为在C和D吃一样东西耗费的时间,然后我们先预处理出第一部分耗费的时间来,然后求一个前缀和(为什么要求前缀和??因为我们最终耗费的时间是在n以内,也就是小于等于n的方案数,如果不计前缀和当前的恰好为正好耗费这个时间的方案数,而这个数组前面的恰好为小于这个时间的方案数,所以我们要处理一个前缀和),然后我们再来枚举吃C和D的哪个美食,然后在累加这种情况下加上A和B以后有多少中情况满足条件,最后输出答案

永利皇宫463娱乐网址 7永利皇宫463娱乐网址 8

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 5010
#define LL long long 
using namespace std;
long long ans;
int n,A,B,C,D,a[N],b[N],c[N],d[N],sum[200000001];
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
 } 
 int main()
 {
     freopen("eat.in","r",stdin);
     freopen("eat.out","w",stdout);
     int minn=0x7fffffff,maxn=0;
    n=read(),A=read(),B=read(),C=read(),D=read();
     for(int i=1;i<=A;i++) a[i]=read();
     for(int i=1;i<=B;i++) b[i]=read();
    for(int i=1;i<=C;i++) c[i]=read(); 
    for(int i=1;i<=D;i++) d[i]=read();
    for(int i=1;i<=A;i++)
     for(int j=1;j<=B;j++)
     {
         sum[a[i]+b[j]]++;
         minn=min(a[i]+b[j],minn);
         maxn=max(a[i]+b[j],maxn);
      } 
    for(int i=minn;i<=maxn;i++) sum[i]+=sum[i-1]; 
    for(int i=1;i<=C;i++)
     for(int j=1;j<=D;j++)
      if(n-c[i]-d[j]>=minn) ans+=(LL)sum[min(n-c[i]-d[j],maxn)];
    printf("%I64d",ans);
     return 0;
 }

AC代码

 发现原来这种可以分成好几部分来做的题可以先分成好几部分与处理一下在做

 

 

 

分糖果(candy)

Time Limit:1000ms   Memory Limit:128MB

 

题目描述

总共有n颗糖果,有3个小朋友分别叫做L,Y,K。每个小朋友想拿到至少k颗糖果,但这三个小朋友有一个共同的特点:对3反感。也就是说,如果某个小朋友拿到3颗,13颗,31颗,333颗这样数量的糖果,他就会不开心。(也即它拿到的糖果数量不包含有一位是3)

LYK掌管着这n颗糖果,它想问你有多少种合理的分配方案使得将这n颗糖果全部分给小朋友且没有小朋友不开心。

例如当n=3,k=1时只有1种分配方案,当n=4,k=1时有3种分配方案分别是112,121,211。当n=7,k=2时则不存在任何一种合法的方案。

当然这个答案可能会很大,你只需输出答案对12345647取模后的结果就可以了。

 

输入格式(candy.in)

第一行两个数表示n,k。

 

输出格式(candy.out)

一个数表示方案总数。

 

输入样例

99999 1

 

输出样例

9521331

 

对于30%的数据n<=100

对于50%的数据n<=1000。

对于另外30%的数据k=1。

对于100%的数据3<=n<=10^10000,1<=k<=n/3,且n,k不包含前导0。

 

 

永利皇宫463娱乐网址 9永利皇宫463娱乐网址 10

/*
一共三个数组成n,我们枚举前两个数,第三个数就可以直接算出来,然后判断这三个数是否满足条件,如果满足条件,ans++
我们用一个pd函数判断这个数是否满足条件,满足条件的情况为每一位上都不含有3
*/ 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
LL n,k,ans;
LL read()
{
    LL x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
bool pd(LL x)
{
    while(x)
    {
        if(x%10==3) return true;
        x/=10;
    }
    return false;
}
int main()
{
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    n=read(),k=read();
    for(int i=k;i<=n-k;i++)
    {
        if(pd(i)) continue;
        for(int j=k;j+i<=n-k;j++)
         if(pd(j)||pd(n-i-j)) continue;
         else ans++;
    }
    printf("%lld",ans);
    return 0;
}

50分的枚举

 

正解:数位dp(本人暂时不想搞dp(主要是脑子笨想不出状态转移来),一段时间后在改吧)

永利皇宫463娱乐网址 11永利皇宫463娱乐网址 12

#include<cstdio>
#include<cstring>
#define N 10003
using namespace std;
const int mod=12345647;
char s[N];
int a[N],b[N],dp[N][3][2][2][2];
void ADD(int &i,int j)  {  i+=j; if(i>=mod) i-=mod; }
int main()
{
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    scanf("%s",s+1); int len1=strlen(s+1);
    for(int i=1;i<=len1;++i) a[i]=s[i]-'0';
    scanf("%s",s+1); int len2=strlen(s+1);
    for(int i=1;i<=len2;++i) b[i+len1-len2]=s[i]-'0';
    dp[0][0][0][0][0]=1;
    int i,j,k,l,t,I,J,K,L,T;
    for(i=0;i<len1;i++)
      for(j=0;j<3;j++)
        for(k=0;k<2;k++)
          for(l=0;l<2;l++)
            for(t=0;t<2;t++)
                if(dp[i][j][k][l][t])
                  for(int s1=0;s1<=9;s1++)
                    if(s1!=3)
                      for(int s2=0;s2<=9;s2++)
                        if(s2!=3)
                          for(int s3=0;s3<=9;s3++)
                            if(s3!=3)
                            {
                                I=i+1;
                                J=j*10+a[i+1]-s1-s2-s3;
                                if(J<0 || J>2) continue;
                                if(!k && s1<b[i+1]) continue;
                                K=(k || s1>b[i+1]);
                                if(!l && s2<b[i+1]) continue;
                                L=(l || s2>b[i+1]);
                                if(!t && s3<b[i+1]) continue;
                                T=(t || s3>b[i+1]);
                                ADD(dp[I][J][K][L][T],dp[i][j][k][l][t]);                    
                            }
    int ans=0;
    for(k=0;k<2;k++)
        for(l=0;l<2;l++)
            for(t=0;t<2;t++)
                ADD(ans,dp[len1][0][k][l][t]);
    printf("%d",ans);                        
}

正解

 

编辑: 操作系统 本文来源:1综合强化刷题,贪心算法推导

关键词: