【程序设计基础_C语言】北理工的恶龙,程序设计基础_c

来源:未知作者:操作系统 日期:2020/03/01 22:10 浏览:

您的帝国里有一条N个头的恶龙,你希望雇佣一些骑兵把它杀死。村里有m个骑士能够雇佣,贰个手艺值为x的铁骑能够砍掉恶龙二个直径不当先x的头,且必要支付x个金币。如何雇佣骑士本领砍掉恶龙的富有头,且须要开支的金币起码?注意,三个骑兵只好砍二个头。输入包涵多组数据。每组数据的第一行为正整数n和m;以下n行每行为一个卡尺头,即恶龙种种头的直径;以下m行每行为二个整数,即各类骑士的力量。输入完结标识为n=m=0。对于每组数据,输出最少开支。假若无解,则输出“Loowaterisdoomed!”。235478421551000

1. 锤练安顿(exercise.pas卡塔尔(قطر‎

人身是革命的本金,OIers不要因为恐慌的求学和成天在Computer前而忽视了符合规律难题。小x设计了和煦的练习布署,但她不了然这些布署是否有效,换句话说即便布署不当恐怕会让她的体力超额支出,所以小x请你补助他。

一天有1440秒钟,所以小x列出的是这一全日第1至第1440秒钟的安排。小x的体力用几个卡尺头来代表,他会依据陈设表举行练习,同不常候,每分钟小x的体力会自动扩充1。如若某一分钟末小x的体力小于等于零,那么可怜的小x就累死了……

 

输入(exercise.in)

先是行是用空格分开的多个整数n,m,分别代表小x的开首体力值和安插的门类数量。

从第二行早前的m行,每行描述四个精雕细刻项目:名称、开端时间a、截至时间b、每分钟消耗的体力(用空格分隔State of Qatar,表示此项目从第a分钟初开首,第b分钟末结束。练习项目依据发轫时间依次增加顺序给出,不会产出多少个连串时间冲突的景色。

 

输出(exercise.out)

       输出富含两行,如若安顿可行,第一行输出"Accepted",第二行输出这一天现在最后剩下的体力;不然在率先行输出"Runtime Error",第二行输出在第几分钟累死。

 

样例

Input

Output

10 1

Basketball 1 10 1

Accepted

1440

1 1

Nunchakus 1 1 2

Runtime Error

1

 

约定

0<n<=2^31-1

0<=m<=500

怀有中间值的断然值不会超越2^31-1

每叁个磨砺项目标名称不超越二十一个字符,此中不含空格。

56net亚洲必赢 156net亚洲必赢 2

/*
    线段树维护每分钟消耗的体力,每个运动相当于一个区间查询
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 510
long long s,a[2000],b[2000];
int n;
char ch[30];
struct node{
    int l,r;
    long long v,lazy;
}tr[maxn<<4];
long long qread(){
    long long i=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch<='9'&&ch>='0'){i=i*10+ch-'0';ch=getchar();}
    return i;
}
void build(int l,int r,int k){
    tr[k].l=l;tr[k].r=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(l,mid,k<<1);
    build(mid+1,r,k<<1|1);
}
void updata(int k){
    if(tr[k].l==tr[k].r)return;
    int l,r;
    long long v=tr[k].lazy;
    l=tr[k<<1].l;r=tr[k<<1].r;
    tr[k<<1].v=(r-l+1)*v;
    tr[k<<1].lazy+=v;

    l=tr[k<<1|1].l,r=tr[k<<1|1].r;
    tr[k<<1|1].v=(r-l+1)*v;
    tr[k<<1|1].lazy+=v;
    tr[k].lazy=0;
}
void change(int l,int r,long long v,int k){
    if(tr[k].l>=l&&tr[k].r<=r){
        tr[k].v+=(tr[k].r-tr[k].l+1)*v;
        tr[k].lazy+=v;
        return;
    }
    if(tr[k].lazy)updata(k);
    int mid=(tr[k].l+tr[k].r)>>1;
    if(l<=mid)change(l,r,v,k<<1);
    if(r>mid)change(l,r,v,k<<1|1);
    tr[k].v=tr[k<<1].v+tr[k<<1|1].v;
}
long long find(int op,int k){
    if(tr[k].l==tr[k].r)return tr[k].v;
    if(tr[k].lazy)updata(k);
    int mid=(tr[k].l+tr[k].r)>>1;
    if(op<=mid)return find(op,k<<1);
    if(op>mid)return find(op,k<<1|1);
    tr[k].v=tr[k<<1].v+tr[k<<1|1].v;
}
int main(){
    //freopen("Cola.txt","r",stdin);
    freopen("exercise.in","r",stdin);
    freopen("exercise.out","w",stdout);
    s=qread();
    scanf("%d",&n);
    int x,y;long long z;
    build(1,1440,1);
    for(int i=1;i<=n;i++){
        scanf("%s%d%d",ch,&x,&y);
        cin>>z;
        change(x,y,z,1);
    }
    for(int i=1;i<=1440;i++)a[i]=find(i,1);
    b[0]=s;
    for(int i=1;i<=1440;i++){
        b[i]=b[i-1]+1;
        b[i]-=a[i];
        if(b[i]<=0){
            printf("Runtime Errorn%d",i);
            return 0;
        }
    }
    printf("Acceptedn%d",b[1440]);
    return 0;
}

100分 线段树

【程序设计根底_C语言】北理工科的恶龙,程序设计根底_c

2.喵星人爬山(catclimb.pas卡塔尔

难点陈诉

Freda和rainbow喂养了N只猫咪,那天,喵星大家要去爬山。涉世了苦大仇深,猫咪们到底爬上了尖峰,然则疲倦的它们再也不想徒步走下山了(呜咕>_<)。

Freda和rainbow只能花钱让它们坐索道下山。索道上的缆车最大承重量为W,而N只猫咪的分占的额数分别是C1、C2……CN。当然,每辆缆车里的猫猫的份量之和不能超越W。每租用一辆缆车,弗瑞德a和rainbow将在付1欧元,所以她们想精晓,起码须要付多少澳元才能把那N只喵咪都运载下山?

输入格式

先是行李包裹蕴三个用空格隔绝的整数,N和W。

接下去N行每行一个卡尺头,个中第i+1行的整数表示第i只猫猫的份量C i。

出口格式

出口壹个子弹头,起码要求有些澳元,也正是起码须求多少辆缆车。

样例输入

5 1996

1

2

1994

12

29

样例输出

2

数码范围与约定

对于100%的数据,1<=N<=18,1<=C i <=W<=10^8。

56net亚洲必赢 356net亚洲必赢 4

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,w,ans,a[20],b[20];
void dfs(int now,int sum){
    if(sum>=ans)return;
    if(now==n+1){
        ans=min(ans,sum);
        return;
    }
    for(int i=1;i<=sum;i++){//往以前用过的背包里装 
        if(b[i]+a[now]<=w){
            b[i]+=a[now];
            dfs(now+1,sum);
            b[i]-=a[now];
        }
    }
    if(sum==n)return;
    b[sum+1]+=a[now];
    dfs(now+1,sum+1);
    b[sum+1]-=a[now];
}
int main(){
    //freopen("Cola.txt","r",stdin);
    freopen("catclimb.in","r",stdin);
    freopen("catclimb.out","w",stdout);
    scanf("%d%d",&n,&w);ans=n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs(1,0);
    printf("%d",ans);
    return 0;
}

74分 暴力

56net亚洲必赢 556net亚洲必赢 6

/*
    暴力之前先从大到小排个序
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,w,ans,a[20],b[20];
void dfs(int now,int sum){
    if(sum>=ans)return;
    if(now==n+1){
        ans=min(ans,sum);
        return;
    }
    for(int i=1;i<=sum;i++){//往以前用过的背包里装 
        if(b[i]+a[now]<=w){
            b[i]+=a[now];
            dfs(now+1,sum);
            b[i]-=a[now];
        }
    }
    if(sum==n)return;
    b[sum+1]+=a[now];
    dfs(now+1,sum+1);
    b[sum+1]-=a[now];
}
bool cmp(int x,int y){
    return x>y;
}
int main(){
    //freopen("Cola.txt","r",stdin);
    freopen("catclimb.in","r",stdin);
    freopen("catclimb.out","w",stdout);
    scanf("%d%d",&n,&w);ans=n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1,cmp);
    dfs(1,0);
    printf("%d",ans);
    return 0;
}

100分

北理工科的恶龙(附qsort实例)

背景: 近几年,北理工科现身了一只恶龙,它长着诸四头,而且还有大概会吐火,它将会把北理工烧成残骸, 于是,校长下令召集全校全数勇士杀死那只恶龙。要干掉这只龙,必需把它装有的头都砍掉,各个勇士只好砍贰个龙头,龙的每种头大小都不均等,叁个勇士独有在身体高度不小于龙头的直径的状态下本领轰下它。并且勇士们供给,砍下七个龙头必得得到和和睦身体高度分米数同样的学分。校长想花 起码的学分数 杀死恶龙,于是找到你寻求援助。

输入: 先是行 龙头数 n , 勇士人数 m ( 1<=n, m<=100 ) 接下来 n 行,每行满含二个平头,表示龙头的直径 接下来 m 行,每行李包裹涵叁个卡尺头,表示勇士的身体高度 l

输出: 借使勇士们能完成任务,输出校长要求花的小不点儿开销;不然输 出 “bit is doomed! ”

 

测验输入 期望的输出 时间范围 内部存款和储蓄器节制额外进度

测验用例 1

以文件方式体现

以文件模式体现

1秒

64M

0

测量检验用例 2

以文件格局显示

以文件方式体现

1秒

56net亚洲必赢 ,64M

0

【分析】 难点抽象为多少个数组,dragon和soldier,分别存款和储蓄勇士的身体高度和龙头的直径。 假如数组soldier中某些值大于等于dragon有个别值,即斩龙头成功,勇士身体高度计入sum。 须要“成本学分”起码,即优先让身体高度十分低的斗士去当前剩下最小的斩龙头,所以先将七个数组分别从小到大排序。 当有龙头剩下(i <= n)且并未有勇士能够斩龙头(j > m)时,战败。 须要注意的一点,要是当前勇士成功斩龙,那么既要向下贰个龙头移动,又要向下三个英雄移步(因为叁个勇士只可以斩八个龙头)。
【代码】

//E026:【大学】北理工的恶龙
#include"stdio.h"
#include"stdlib.h"

int cmp(const void *a, const void *b)  //排序函数 
{
 return *(int *)a - *(int *)b;
}

int cmp(const void *a, const void *b);

int main()
{
 int n; //n是龙头数
 int dragon[102] = { 0 }; //dragon是龙头的直径
 int m; //m是勇士人数
 int soldier[102] = { 0 }; //solider是勇士的身高
 int sum = 0; //sum是花费的总学分数(斩龙的用时身高之和)
 int i, j;

 scanf("%d %d", &n, &m);
 for (i = 1; i <= n; i++) //输入龙头直径
 {
  scanf("%d", &dragon[i]);
 }
 for (i = 1; i <= m; i++) //输入勇士身高
 {
  scanf("%d", &soldier[i]);
 }
 qsort(dragon+1, n, sizeof(int), cmp);  //调用函数,为dragon排序
 qsort(soldier+1, m, sizeof(int), cmp);  //调用函数,为soldier排序
/*
 for (i = 1; i <= n; i++) //监视排序是否成功 -- 成功
 {
  printf("dragon[%d] = %dn", i, dragon[i]);
 }
*/
 for (i = 1, j = 1; i <= n; i++)
 {
  //printf("i = %dn", i); //监视i的值
  if (j > m)
  {
   //printf("Failure:i = %d, j = %dn", i, j); //监视失败时的状况
   goto failure;
  }

  if (soldier[j] >= dragon[i]) //如果当前的勇士能够斩龙头
  {
   sum += soldier[j];
   j++; //成功则该勇士计入sum,并比较下一个勇士和下一个龙头
   //printf("勇士i = %d 斩龙j = %d成功!n", i, j); //标明斩龙头成功
   continue;
  }
  else //如果当前的勇士不能斩龙,那么循环直到斩龙成功,或者失败
  {
   while (soldier[j] < dragon[i]) //如果当前的勇士不能斩龙,该勇士不计入sum,并比较下一个勇士
   {
    j++;
    if (j > m) //如果没有下一个勇士了,则失败
     goto failure;
    else if (soldier[j] >= dragon[i]) //比较下一个勇士
    {
     sum += soldier[j];
     j++;
     break; //成功则该勇士计入sum,并比较下一个勇士和下一个龙头
    }
    else
    {
     continue; //如果该勇士也失败,比较下一个勇士
    }
   }
  }
 }
 printf("%dn", sum);
 return 0;

failure:
 printf("bit is doomed!n");
 return 0;
}//main