XMU oj Problem List

glm233

发布于 2020-09-28 10:18:50

6310

发布于 2020-09-28 10:18:50

文章被收录于专栏：glm的全栈学习之路glm的全栈学习之路

1000

请计算两个整数的和并输出结果。

注意不要有不必要的输出，比如"请输入 a 和 b 的值: "，示例代码见隐藏部分。

#include <stdio.h>
int main(){
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a+b);
    return 0;
}

1111

有n只怪兽，每个怪兽有一个HP[i].商店有m个不同的水果，用来砸怪兽。水果有一个杀伤力val和一个价格pri，当某一个水果的杀伤力大于或者等于怪兽的HP的时候该怪兽会被消灭。一个水果只能用来砸一只怪兽，一个怪兽也只能被一个水果砸。求使得所有怪兽被消灭的最小花费。

Input

第一行两个正整数n，m（1<=n,m<=50005）接下来一行n个正整数，表示n个怪兽们的HP(1<=HP<=100000)接下来m行每行两个正整数val，pri，表示第i种水果的杀伤力和价格。(1<=val,pri<=100000)

Sample Input 1 Sample Output 1

3 3 6 1 2 3 2 1 3 2 4 3

#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
long long f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
struct node
{
    int hp;
    int val;
}f[1000005];
bool cmp(node a,node b){return a.val<b.val;}
int n,m,a[500005],ans,flagg[1000005];
int main()
{
read(n),read(m);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<=m;i++)read(f[i].hp),read(f[i].val);
sort(f+1,f+1+m,cmp);
for(int i=n;i>=1;i--)
{
    int flag=1;
    for(int j=1;j<=m;j++)
    {
        if(flagg[j]==0&&a[i]<=f[j].hp){ans+=f[j].val,flag=0;flagg[j]=1;break;}
    }
    if(flag)
    {
        cout<<"No Solution"<<endl;
        return 0;
    }
}
cout<<ans<<endl;
    return 0;
}

1112

Description

你需要实现一个数据结构。该数据结构有n个正整数，需要实现两种操作。1.修改操作，将第x个数的数值减小y2.查询操作，查询n个正整数中最大的正整数的值。

Input

第一行一个正整数n表示你有n个正整数。接下来一行n个正整数a[1]...a[n]，表示这n个正整数的值。接下来一个正整数m 表示操作的次数接下来每行描述一个命令:第一个正整数如果为0，则接下来输入两个正整数x y，表示将第x个数的数值减小y。第一个正整数如果为1,则表示查询操作，查询n个正整数中最大的正整数的值。

Output

对于每一个查询操作，输出一行一个正整数。即每次查询时n个正整数中最大的正整数。

Sample Input 1

3
234 12 123123 
3
0
1 3 123120
0

Sample Output 1

123123
234

本题没有代码，Brutal Force即可，1000ms过不了，月赛的时候是3s的...

1113

拆分

Description

给你一堆数：1, 1, 2, 2, 4, 4, ..., 2^k, 2^k（即双份的2的非负整数次幂），再给你一个非负整数n，满足2^k>=n。现将n拆分成这些数中若干个数的和，求拆分方案数。

Input

一个整数n，0<n<10^18

Output

一个整数，即拆分方案数。

Sample Input 1

Sample Output 1

dp[i]=dp[i/2] (if(i%2))
else
{
 dp[i]=dp[i/2]+dp[i/2-1]
}
不过dp内存会炸
用不定长数组vector
状态转移方程？
多写几项就发现了
#include <iostream>
#include <vector>
#include<cstdio>

using namespace std;
typedef unsigned long long ULL;
typedef std::pair<ULL, ULL> Pair;  // 用一个数对来记录状态

vector<Pair> vis;  // 用vector来模拟线性数据结构

ULL check(ULL n) {  // 没有优化的粗暴查询
 vector<pair<ULL,ULL> > ::iterator iter;
for(iter=vis.begin();iter!=vis.end();iter++)
{
        if ((*iter).first == n)
            return (*iter).second;
    }
    return -1;
}

ULL solve(ULL n) {  // 淳朴的递归，但并不盲目
    if (check(n) != -1)
        return check(n);
    else if (n & 1) {
        ULL ans = solve(n -1)+1;
        vis.push_back(Pair(n, ans));
        return ans;
    } else {
        ULL ans = 3*solve(n >> 1);
        vis.push_back(Pair(n, ans));
        return ans;
    }
}

int main() {
int n;
    vis.push_back(Pair(1, 1));
   vis.push_back(Pair(2, 3));
    vis.push_back(Pair(3, 4));
   while(~scanf("%d",&n))
   {
 ULL ans = solve(n);
    cout << ans << endl;
   }
    return 0;
}

1004 夸夸群 Description 虽然夸夸群里的每个人小嘴都像抹了蜜一样甜，但是被夸的人却不一定开心，因为每个人的“夸点”不同！刘学习的夸点就非常奇怪，他会把别人夸他的每个字进行量化得到一个非负整数序列A。刘学习定义夸夸序列为：1、夸夸序列是A中的一段连续子序列。2、夸夸序列中的最大值和最小值满足a<=最大值-最小值<=b。已知刘学习的开心值=A中最长夸夸序列的长度。现在告诉你将夸夸群中的一段话量化得到的非负整数序列A，请计算出刘学习的开心值。 Input 第一行一个非负整数n，表示序列A的长度，1<=n<=1000000.第二行两个非负整数a，b，含义如题，0<=a, b<= 100000000.接下来一行共有n个整数，即为序列A，0<=序列中每个数<=100000000. Output 一个整数，表示刘学习的开心值。 Sample Input 1 6 1 3 1 2 3 4 5 6 Sample Output 1 4

#include<bits/stdc++.h>
using namespace std;
int a[1000005],n,m,k,ans=1,last;
deque <int>maxq,minq;
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!maxq.empty()&&a[maxq.back()]<=a[i])maxq.pop_back();
        maxq.push_back(i);
        while(!minq.empty()&&a[minq.back()]>=a[i])minq.pop_back();
        minq.push_back(i);
        while(!maxq.empty()&&!minq.empty()&&(a[maxq.front()]-a[minq.front()])>k)
        {
            if(maxq.front()<minq.front())
            {
                last=maxq.front();
                maxq.pop_front();
            }
            else
            {
                 last=minq.front();
                minq.pop_front();
            }
        }
       if(!maxq.empty()&&!minq.empty()&&(a[maxq.front()]-a[minq.front()])>=m)
        {
            ans=max(ans,i-last);
        }
    }
    cout<<ans<<endl;
    return 0;
}

1115

生成树游戏

Description

滑稽树上滑稽果滑稽树下你和我滑稽树前做游戏滑稽树后做交易

Description

A和B看到滑稽树，有感而发，于是做起了游戏。游戏规则是这样的：首先给定一个无向连通图，边权是0或者1。然后B选择这张图的其中一棵生成树，A的目的是要通过尽量少的步数，猜出这个生成树边的总权值。每次A猜测一个数，如果刚好猜对，那么B会告诉A猜对了，否则就会告诉A这个数是大了还是小了。A想知道在最坏情况下需要几步猜出。

Input

第一行一个整数T，表示数据组数(T<=10)。接下来T组数据，每组数据构成如下：第一行两个整数n,m(2<=n<=100000,n-1<=m<=200000)，表示所给连通无向图的点数和边数。接下来m行每行三个整数s,t,w(1<=s,t<=n,0<=w<=1)，表示一条边起终点是s,t，权值为w。

Output

按照输入顺序，对于每一组数据，输出对应的最小步数。

Sample Input 1

1
2 1
1 2 0

Sample Output 1

带师兄出的题，占坑待填。。。。。

填好了。。

#include<bits/stdc++.h>
using namespace std;
const int inf=999999999;
int n,m,q,t,fa[100005];
struct edge{
    int x,y,len;
}e[200005];
bool cmp1(edge a,edge b){
    return a.len>b.len;
}
bool cmp2(edge a,edge b){
    return a.len<b.len;
}
int find(int x){
    return fa[x] != x ? fa[x] = find(fa[x]) : x;
}
int kruskal1(){
    for(int i=0;i<=n;i++)
        fa[i]=i;
    sort(e,e+m,cmp1);
    int cnt=0;
    int sum=0;
    for(int i=0;i<m;i++){
        int x=e[i].x,y=e[i].y;
        int t1=find(e[i].x);
        int t2=find(e[i].y);
        if(t1!=t2){
            sum+=e[i].len;
            fa[t2]=t1;
            cnt++;
        }
        if(cnt==n-1)
            break;
    }
    if(cnt<n-1)

        return -1;
    else
        return sum;
}
int kruskal2(){
    for(int i=0;i<=n;i++)
        fa[i]=i;
    sort(e,e+m,cmp2);
    int cnt=0;
    int sum=0;
    for(int i=0;i<m;i++){
        int x=e[i].x,y=e[i].y;
        int t1=find(e[i].x);
        int t2=find(e[i].y);
        if(t1!=t2){
            sum+=e[i].len;
            fa[t2]=t1;
            cnt++;
        }
        if(cnt==n-1)
            break;
    }
    if(cnt<n-1)

        return -1;
    else
        return sum;
}
int main(){

cin>>t;
while(t--)
{
    scanf("%d%d",&n,&m);

    for(int i=0;i<m;i++)

        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].len);

   /* printf("%d\n",kruskal1());
    printf("%d\n",kruskal2());*/
    int k=kruskal1()-kruskal2()+1;
cout<<(int)log2(k)<<endl;
}
return 0;
}

1001

宅男健身计划

Description

宅男TheBeet有一天心血来潮发誓要开始锻炼身体，他给自己订了一个计划：他在宿舍的中间摆了一个椅子，今天也就是第0天绕着椅子跑1圈，明天也就是第1天绕着椅子跑2圈，后天也就是第2天绕着椅子跑4圈，大后天也就是第3天跑8圈……以后每天跑的圈数是前一天的两倍。TheBeet对自己的计划信心满满，认为自己肯定能坚持下去。但是TheBeet数学不太好，今天是他定下计划的第N天，您来告诉他今天到底要跑多少圈。

Input

输入一个正数字N(0 <= N <= 30)。

Output

输出TheBeet要跑的圈数。

Sample Input 1

Sample Output 1

#include<bits/stdc++.h>
using namespace std;
inline void read(long long &x)
{
long long f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
long long n,temp=1;
inline int quickpow(int a,int b)
{
    if(b<=0)return 1;
    if(b==1)return a;
    return quickpow(a*a,b/2)*(int)pow(a,b%2);
}
int main()
{
    read(n);
cout<<quickpow(2,n)<<endl;
    return 0;
}

1002

C=?+?

Description

Input c,

Output a and b that a + b = c

Input

a signed 32bit integer c

Output

Output just one pair of signed 32bit integers a and b.

#include<bits/stdc++.h>
using namespace std;
inline void read(long long &x)
{
long long f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
long long n,temp=1;
long long a[5000005];
int main()
{
    read(n);
cout<<0<<" "<<n<<endl;
    return 0;
}

1003

Sort

Description

Give a set of numbers, output them after sort. You may use any algorithm you like to solve it.

Input

Each input file contains only one case.

Each test case begins with an integer N(0<N<=1000), the size of the set.

The Next line contains N numbers, represent the elements of the set. Each number range in [0..65535]

Output

Output the set in one line after sort.

Each pair of adjacent numbers is separated by one space. There is no space but '\n' at the end of the line.

Sample Input 1

4
4 15 8 5

Sample Output 1

4 5 8 15

#include<bits/stdc++.h>
using namespace std;
inline void read(long long &x)
{
long long f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
long long n,temp=1;
long long a[5000005];
int main()
{
    read(n);
for(int i=1;i<=n;i++)read(a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

1004

Sort Ver.2

Description

Give a set of numbers, output them after sort. You may use any algorithm you like to solve it.

Input

Each input file contains only one case.

Each test case begins with an integer N(0<N<=1,000,000), the size of the set.

The Next line contains N numbers, represent the elements of the set. Each number range in [0..2147483647]

Output

Output the set in one line after sort.

Sample Input 1

4
4 15 8 5

Sample Output 1

4 5 8 15

#include<bits/stdc++.h>
using namespace std;
inline void read(long long &x)
{
long long f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
long long n,temp=1;
long long a[5000005];
int main()
{
    read(n);
for(int i=1;i<=n;i++)read(a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

1005

Complete Permutation

Description

Generate the complete permutation of 1..N

Input

Each input file contains only one non-negative integer N (0< N < 9)

Output

Output N! Lines, according tolexicographicorder.

Sample Input 1

Sample Output 1

#include<bits/stdc++.h>
using namespace std;
inline void read(long long &x)
{
long long f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
long long n,flag[15],a[15];
void dfs(int x)
{
    if(x==n+1)
    {
        for(int i=1;i<=n;i++)
        {
            i==n?cout<<a[i]<<" ":cout<<a[i]<<" ";
        }cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!flag[i])
        {
            a[x]=i;
            flag[i]=1;
            dfs(x+1);
            flag[i]=0;
        }
    }
}
int main()
{
read(n);
for(int i=1;i<=n;i++)a[i]=i;
do
{
       for(int i=1;i<=n;i++)
        {
            i!=n?cout<<a[i]<<" ":cout<<a[i];
        }cout<<endl;
}while(next_permutation(a+1,a+1+n));
    return 0;
}

1007

A*B Big Number

Description

Calculate a*b

Input

Two integer a,b(0 <= a,b <= 10^{1000}101000)

Output

Output a * b

Sample Input 1

5 7

Sample Output 1

#include<bits/stdc++.h>
using namespace std;
string a,b;
int d[100000],e[100000];
int l,ll,c[100000];
int main()
{
cin>>a>>b;
l=a.size();
ll=b.size();
for(int i=0;i<l;i++)
{
    d[i]=a[i]-'0';
}
for(int i=0;i<ll;i++)
{
    e[i]=b[i]-'0';
}
for(int i=0;i<l;i++)
{
    for(int j=0;j<ll;j++)
    {
        c[i+j]+=d[i]*e[j];
    }
}
for(int i=l+ll-1;i>0;i--)
{
    if(c[i]>=10)
    {
    c[i-1]+=c[i]/10;
    c[i]%=10;
    }
}
int p=1;
for(int i=0;i<l+ll-1;i++)
{
    if(c[i])p=0;
    if(p==0)
    cout<<c[i];
}
if(p==1)printf("0");
    return 0;
}

1008

N Queens Chess Problem

1010

umber Triangles

Description

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

3 8

8 1 0

2 7 4 4

4 5 2 6 5

In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

Input

The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.

Output

A single line containing the largest sum using the traversal specified.

Sample Input 1

Sample Output 1

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[1005][1005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=i;j++)
    {
        cin>>a[i][j];
    }
}
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=i;j++)
    {
    if(j==1)a[i][j]+=a[i-1][j];
    else if(i==j)a[i][j]+=a[i-1][j-1];
    else a[i][j]+=max(a[i-1][j],a[i-1][j-1]);
    }
}
for(int i=1;i<=n;i++)
{
    ans=max(ans,a[n][i]);
}
cout<<ans;
    return 0;
}

1017

Incomplete Chessboard

1022

矩阵乘法

Description

给出两个的矩阵，求他们的乘积

Input

第一行有两个正整数N_{1}N1, M_{1}M1 (0< N_{1}N1, M_{1}M1 <=100)接下来有N_{1}N1行，每行有M_{1}M1个数字，描述第1个矩阵。

第N+2行有两个正整数N_{2}N2, M_{2}M2 (0< N_{2}N2, M_{2}M2 <=100)接下来有N_{1}N1行，每行有M_{2}M2个数字，描述第2个矩阵。

矩阵的每个元素在[-300, 300]之间，输入保证M_{1}M1等于N_{2}N2。

Output

输出N_{1}N1行每行M_{2}M2个数字表示结果矩阵。每行中每个数字之间用一个空格隔开。

Sample Input 1

Sample Output 1

1 2 4
4 5 10
7 8 16

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios::sync_with_stdio(false);
	ll ai,aj;
	cin>>ai>>aj;
	ll a[ai][aj];
	for(int i=0;i<ai;i++)
		for(int j=0;j<aj;j++)
			cin>>a[i][j];
	ll bi,bj;
	cin>>bi>>bj;
	ll b[bi][bj];
	for(int i=0;i<bi;i++)
		for(int j=0;j<bj;j++)
			cin>>b[i][j];
	for(int i=0;i<ai;i++){
		for(int j=0;j<bj;j++){
			ll sum = 0;
			for(int k=0;k<aj;k++){
				sum += a[i][k] * b[k][j];
			}
			j!=bj-1?cout<<sum<<" ":cout<<sum;
		}
		cout<<endl;
	}
	return 0;
}

1028

Game Boy Advance

Description

TheBeet很喜欢玩GBA游戏。他的手机上有一个GBA的模拟器，可以模拟很多GBA的游戏。今天TheBeet找到了一个GBA Rom下载的网站，里面有很多很多很多很多很多的GBA Rom，每个游戏都有了大小mi和一个TheBeet认为它好玩的程度vi。TheBeet当然是想把它们全部下载过来，但是TheBeet手机的SD卡空闲容量有限，只有M的容量。现在TheBeet想使手机里面保存的所有游戏好玩程度的总和最大，但是面对如此多的游戏，他放弃了。您能帮帮他么?

Input

每个输入文件的第一行有两个正整数N(0<N<=1000),M(64<=M<=8192)，分别表示可供下载的游戏的数目和SD卡的空闲容量。

第二行包含N个正整数，表示每个游戏的大小mi(1<=mi<=1024)。

第三行包含N个整数vi(-10000<=vi<=10000)，表示每个游戏的好玩程度。（负数表示TheBeet讨厌这个游戏）

Output

输出一个保存游戏的方案。第一行是TheBeet手机存的游戏总数目T。接下来那一行您应该输出T个正整数，表示每个游戏的编号（编号从1开始）。如果存在多个方案的最大值相同，那么您只需要输出其中任意一个。

Sample Input 1

5 128
16 128 1024 64 50
101 200 10000 150 -100

Sample Output 1

2
1 4

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[1100][10000],w[1005],v[1005],cnt,ans[1005];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;j++)
    {
        dp[i][j]=dp[i-1][j];
        if(j>=w[i])
        dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
    }
}
int temp=0,j=m;
for(int i=n;i>=1;i--)
{
    j-=temp;
    temp=0;
    if(j>=w[i]&&dp[i][j]==dp[i-1][j-w[i]]+v[i])
    {
        ans[++cnt]=i;
        temp=w[i];
    }
}
cout<<cnt<<endl;
for(int i=cnt;i>=1;i--)
{
    i!=1?cout<<ans[i]<<" ":cout<<ans[i]<<endl;
}
	return 0;
}

1029

矩阵链乘法

Description

给定一个有N个矩阵的矩阵链A_{1}A1 A_{2}A2 A_{3}A3 ... A_{n}An，矩A_{i}Ai的维数为p_{i-1} × p_{i}pi−1×pi。我们都知道，使用朴素的矩阵乘法去乘两个维数分别为x,y和y,z的矩阵，所需要的乘法次数为x × y × z。矩阵链乘法问题就是如何对矩阵乘积加括号，使得它们的乘法次数达到最少。

Input

输入的第一行为一个正整数N(1 <= N <= 200)。表示矩阵的个数。输入的第二行包含N+1个整数，分别表示p_{i}pi(0 <= i <= N)，其中每个p_{i}pi在[1,200]范围内。

Output

输出一个整数表示最少要进行的乘法次数。

Sample Input 1

3
1 2 3 4

Sample Output 1

1030

苦恼的月下老人

Description

传说中，月老是掌管男女婚姻之神。每年七夕，七星娘娘会把人世间未婚的成年男女制成名册，向天庭呈报。月下老人收到名册后，按照个性、善恶、兴趣与条件抄写成一本配偶名册，然后用红线绑牢男女二人之足，使合适的男女配成一对佳偶。在一个古老的小镇，有一条古老的小河横穿这个镇南北，把这个小镇划分成东西两个部分。这个古老的小镇保留着一个古老的风俗，所有未婚男子都住在这条河的西岸上面，所有的未婚女子都住在这条河的东岸。今年月下老人收到了这个小镇上所有未婚男女的名册，他把每个人的个性、善恶、兴趣与条件做了一个简单的汇总，给每个人添加了一个如A B C之类的标签，只有相同标签的男女才有可能用红线绑在一起。原本这个是个很简单的事情，但是现在问题是月老使用的红线，是不能互相交叉的，否则后果会很严重。所以月老为了更多人的幸福，他只能牺牲部分人的幸福。现在月老在纸上笔划了很久，还是没能比划出一个最好的方案，使得让最多对情侣终成眷属。您能帮帮他么？

Input

输入的文件的第一行包含两个整数N,M(0 < N, M <= 1000)，分别表示未婚男子和未婚女子的数目。第二行包含一个长度为N的字符串，字符串为大写字母A-Z和小写字母a-z组成，从北到南顺序表示每个男子的标签。第三行包含一个长度为M的字符串，从北到南顺序顺序表示每个女子的标签。

Output

输出一个整数表示月老最多可以为多少对情侣成功牵线。

Sample Input 1

5 4
ABACB
CBAB

Sample Output 1

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1005][1005];
char a[1005],b[1005];
int main()
{
	cin>>n>>m;
scanf("%s%s",a+1,b+1);
		//cout<<a+1<<endl;
		//cout<<b+1<<endl;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
			    f[i][j]=max(f[i-1][j],f[i][j-1]);
				if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
			}
		}
		printf("%d\n",f[n][m]);

	return 0;
}

1062

山东煎饼

Description

今天TheBeet去门口那家山东煎饼小摊买煎饼，到他付钱的时候他才发现，他的钱包里面只有一张100块。于是他需要把这张100块钱破开，但是TheBeet不喜欢硬币，另外由于某种原因，TheBeet也不喜欢20元的纸币，另外也不喜欢钱包里面有太多张纸币，所以他希望拿到尽量少的纸币数。给出摊主现有的纸币数量，求摊主要如何找零给TheBeet才能满足他的要求。

Input

输入的第一行是一个正整数N(1 <= N <= 40)，表示TheBeet买了N个山东煎饼，已知每个山东煎饼价格为2.5元。接下来有6个非负整数，范围在[0, 1000]之内，分别表示摊主所拥有的50元、10元、5元、1元、5角、1角纸币的数量。

Output

输出一个整数，表示TheBeet最后收到的纸币数。如果无法满足要求，那就输出-1。

Sample Input 1

2
100 100 100 100 100 100

Sample Output 1

Hint

最后TheBeet共收到50+10+10+10+10+5元钱。所以共6张纸币。

#include<bits/stdc++.h>
using namespace std;
int n,ans,x;
struct node
{
    int num,val;
}k[10];
int main()
{
cin>>n;
x=1000-25*n;
for(int i=1;i<=6;i++)
{
    cin>>k[i].num;
    if(i==1)k[i].val=500;
    if(i==2)k[i].val=100;
    if(i==3)k[i].val=50;
    if(i==4)k[i].val=10;
    if(i==5)k[i].val=5;
    if(i==6)k[i].val=1;
}
for(int i=1;i<=6;i++)
{
    while(x>=k[i].val&&k[i].num)
    {
        ans++;
        x-=k[i].val;
      k[i].num--;
    }
}
if(x)
{
     cout<<-1;
    return 0;
}
else
{
    cout<<ans;
    return 0;
}
	return 0;
}

1063
1064
1067
1111
1112
1113
1114
1115

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-04-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

游戏

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

游戏

登录后参与评论

0 条评论

热度