Tyvj2017清北冬令营入学测试

 

 

 

 

 

P4744 A’s problem(a)

时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试题,每三上结算一次于成绩。参与享优惠

描述

这是一样道来背景的问题,小A也是一个起故事的人。但心疼的是此处纸张太小,小A无法拿故事详细地说让大家听。可能小A自己为摆不知晓自己之故事,因为如果出口清了,也便没有就道问题了……

小A的问题是者样子,它找到了n份不同之做事,第i份工作每个月有ai的工钱,每卖工作需小A每天工作8钟头,一圆满工作7天。小A想知道性价比最高(一个月的工资除以总时长)的做事之数码是有些。如果出多卖,输出编号最小之饶足以了。

输入格式

率先执一个数n,表示有n份工作。

         接下来n个数表示ai。

输出格式

输出一个往往表示答案。

备注

输入样例

5

3 3 4 5 5

 

输出样例

4

 

数码范围

对于100%的数据n<=100,1<=ai<=1000。

 【水题不多说系列】

#include<iostream>
using namespace std;
int n,a[110];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int j=1;
    for(int i=2;i<=n;i++)
        if(a[i]>a[j])j=i;
    cout<<j;
    return 0;
}

P4745 B’s problem(b)

时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试

描述

题目叙述

         小B在在一个分外意外的国里,这个国度之钱之面值才来或是25,50,100的。小B最近于召开社会实践,这次它选择当一个食堂里提到这件工作。但今天来了相同码有趣之事,这宗事情是这样子的,餐厅里大家都以排队买饭,粗心的起饭阿姨忘记要带零钱,并且有排队从饭的人口单纯带了平等张钱。

         具体地,第i私家带了相同张面额为ai的钱,为了有利于起见,我们确定每个人犹惦记购入价值25长之饭盒。阿姨显得不知所措。聪明的小B想到了一个法,让带了25正之先期打饭!这样阿姨就有矣再多之零花钱去寻找起来部分面值较充分之钱。

         但这样于部分人数的话仍发生或寻不起来零钱,小B想知道是不是有同样栽排队方案,能够对持有人摸开零钱。如果中输出“YES”,否则输出“NO”。

输入格式

首先尽一个数n,表示有n个想进饭的食指。

         接下来一行n个数ai,表示第i私带在的钱之面额。

 

输出格式

输出“YES”或者“NO”。

 

备注

输入样例

3

25 50 100

 

出口样例

NO

 

数量范围

对于100%的数据n<=100,ai=25或者50或者100。

 思路

把具备的丁用的钱从小到很破个程序,另外可以窥见

若果是人将的是25第一,那么不需要寻找钱,我之钱管里即使基本上了25元

假如这人用的凡50冠,那么就发生同等种解决办法,用同摆设25处女的与他换,如果此时我从不25最先的那么“NO”(因为自曾拿人们从杀到稍微散过序了,所以后面的人头非容许有25底钱)

如是人以的凡100首位,有少数栽办法

  用一张50和一张25与他换,要求b25>=1,b50>=1

  用三张25与他换,要求b25>=3

切莫满足要求则NO

#include<iostream>
#include<algorithm>
using namespace std;
int n,a[110],b25,b50,b100;
bool flag;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        if(a[i]==25)b25++;
        if(a[i]==50)
        {
            if(b25==0)flag=1;
            else b25--,b50++;
        }
        if(a[i]==100)
        {
            if(b25==0)flag=1;
            else{
                if(b25>=1&&b50>=1){
                    b25--;b50--;
                    continue;
                }
                else if(b25>=3){
                    b25-=3;
                    continue;
                }
                else flag=1;
            }
        }
    }
    if(flag==0)cout<<"YES";
    else cout<<"NO";
    return 0;
}

 

P4747 D’s problem(d)

时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试题

描述

题目叙述

         小D是一样称作魔法师,它无限欢喜干的从业就是是针对性批记者了。

         这次记者招待会上,记者对小D的数学好好奇。于是小D找了个法子将记者批判了同一胡。

         它对记者抛来了这般一个问题:我有n点能量,写下数字i(1<=i<=9)需要花费a{i}点能量,我之所以就n点能量最多克写来什么数来?(当然可以无用光n点能量,具体看样例)

         记者等一样面子懵逼,于是来求助于你。

输入格式

一行10个数,表示n,a1,a2,a3,…,a9。

输出格式

一个反复表示答案。

备注

输入样例1

10 2 2 1 2 2 2 2 2 2

 

输出样例1

3333333333

 

输入样例2

10 4 11 11 11 11 11 11 11 10

 

出口样例2

11    

 

数码范围

对于30%的数据n,ai<=10。

对于60%的数据n,ai<=100。

对于100% 的数据1<=n,ai<=1000000,n>=min{ai}。

思路

输出的勤最好充分,首先要确保输出的位数最可怜,其次要尽量要高位上的数值最深

找到数列中之极端小值,即可找到出口的极度充分位数=总能/最小值

或是于出口一拧最小值代表的职后发现还有能剩余,那么这些能量不用白不用,但是我们输出的数字已是故能最小的数字了,没有还有些之供自己单独行使剩余能量了,于是自己只好待去头规定的数列中改变部分频,当然,为了不进一步转越聊,我们要由9反倒在循环,到最好小值就截止。

至于落实,我们只需要同涂鸦同涂鸦的长余数,然后以算中获取新的余数,我以代码中说之比较清楚

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,t;
int a[2000000];
int min1=99999999;
int flag=1;
int main()
{
    cin>>n;
    for(int i=1;i<=9;i++)cin>>a[i];
    for(int i=9;i>=1;i--)
    {
        if(a[i]<min1)
        {
            min1=a[i];//找到最小数的大小min1和序号t 
            t=i;
        }
    } 
    int s=n/a[t];//最多可以输出s个t 
    int q=n%a[t];//输出s个t后,还剩q个能量 
    int p=0;
    for(int j=1;j<=s;j++)
    {    
        q+=min1;//剩下的能量加上输出这个位置上的t所需要的能量,可能得到更优的解,933总比333优吧,那就把输出333剩下的能量分配出一点来供给输出9,还得保证输出数字的位数不变 
        for(int i=9;i>=t;i--)//从9到t中寻找更划算 
            if(a[i]<=q)
            {
                q=q-a[i];//我又计算出一个新的剩余能量 
                cout<<i;
                p++;//p代表了被我修改(用剩余能量补偿至>t)的数的个数 
            }
    }
    for(int i=1;i<=s-p;i++)cout<<t;//把未经修改的位置上填满t 
    return 0;
}

 

P4749 F’s problem(f)

时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试

描述

夫故事是有关小F的,它发一个怎么样的故事呢。

         小F是一个田径爱好者,这天她都里刚以开马拉松赛,这个城池可以于用作是n个点m条带权有往无尽做的觊觎。马拉松比赛的顶点就生一个:点S。

         有k个人与会了当下会长期,小F所当的市的漫漫及正规的久远不一致,每个人之起点都是未等同的,具体地,第i私房自第{ai}个市出发,并且第i个人的快慢是{vi}。每个人本来是会顺着最差里程走至S点,如果一个人数跑的相距是s,速度是v,那么他所花的年华吧s/v。

         现在小F想知道,谁是最好抢至顶峰的。若发生差不多只又抵达极限的,就请跑的里程最丰富之,如果起差不多个同时到达极限还跑的路最丰富之,就伸手编号最特别的。

         小F想掌握死人的号码是稍微。

 

输入格式

第一履行3独数字,n,k,m,表示点之个数,跑步的口,以及路径的条数。

         接下来一行m行,每行3个数ai,bi,ci代表来同等长长的从ai到bi长为ci的发于路。

         接下来一样实行一个数S。

         接下来一样履行k个数,表示每个人之起点xi。

         接下来一样实施k个数,表示每个人之速度vi。

出口格式

输出一个频表示答案。

 

测试样例1

输入

5 2 10 
5 1 9 
1 2 81 
2 3 30 
2 1 46 
1 4 45 
2 4 48 
5 1 93 
2 5 61 
2 5 21 
3 5 45 

3 5 
18 29

输出

2

备注

输入样例

3 2 3

1 2 2

1 3 3

2 3 1

3

2 1

1 3

 

输出样例

2

 

多少范围

对于30%的数据n<=5,m<=10。

对于100%的数据n<=300,m<=5000。0<=ci<=100,1<=xi,S<=n,1<=vi<=100,1<=k<=n。

 思路

数据范围好xiao,本少大放心头的快,写了一致篇弗洛伊德

弗洛伊德求出最好缺少里程。then balabala……(都以代码中了)

#include<iostream>
using namespace std;
int a[301][301];
int n,k,m,s;
int x,y,z;
int xi[301],vi[301];
double minx=999999;
int jl,jlk;
int main()
{
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]==0&&i!=j) a[i][j]=999999;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        a[x][y]=z;
    }
    for(int kk=1;kk<=n;kk++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(i!=j&&i!=kk&&j!=kk)
                {
                    a[i][j]=min(a[i][j],a[i][kk]+a[kk][j]);
                }
            }
    cin>>s;
    for(int i=1;i<=k;i++)
        cin>>xi[i];
    for(int i=1;i<=k;i++)
        cin>>vi[i];
    for(int i=1;i<=k;i++)
    {
        if(a[xi[i]][s]*1.0/vi[i]<=minx)
        {
            if(a[xi[i]][s]*1.0/vi[i]==minx)
            {
                if(a[xi[i]][s]>=a[jlk][s])
                {
                    minx=a[xi[i]][s]*1.0/vi[i];
                    jl=i;
                    jlk=xi[i];
                }
            }
            else{
                minx=a[xi[i]][s]*1.0/vi[i];
                jl=i;
                jlk=xi[i];
            }
        }
    }
    cout<<jl;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注