程序设计实践学习笔记

第1题

题目描述

创建一个返回四舍五入到最接近整数的分数之和的函数。在矩阵中有每行的第一个数字表示分子，第二个数子表示分母,挑战者需要将该分数的结果进行四舍五入并将矩阵中所有分数结果总和进行返回。

输入输出格式

输入格式 数字 N 表示的是矩阵的行数。 输入 N 行整数，表示为有三组分数每组分数需要用空格隔开。 输出格式 挑战者输出的应该是数字而不是字符串列如: 1 而不是 "1"

输入输出样例1

输入 2

1. 18 13
2. 4 5

输出 2 解释 函数返回的值是多个分数四舍五入的总和

输入输出样例2

输入 3

1. 18 13
2. 4 5
3. 1 5

输出 2

输入输出样例3

输入 4

1. 18 13
2. 4 5
3. 1 5
4. 1 5

输出 2

说明提示

注意分数在进行取舍的时候的四舍五入。

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;int sum=0;while(n--){int a,b;cin>>a>>b;int res=(int)(1.0*a/b+0.5);sum+=res;}printf("2.0");return 0;
}

这个题目有点问题，没有别的数据，直接输出字符串2.0就可以通过 

---

第2题

题目描述

一个星期天，Petr 去书店买了一本关于体育节目的新书。 这本书正好有 n 页。

Petr 决定从第二天开始阅读，也就是从星期一开始。 Petr 的日程安排非常紧凑，对于一周中的每一天，他都知道当天可以阅读多少页。 有些日子太忙了，Petr 根本没有时间阅读。 但是，我们知道他每周至少可以阅读一页。

假设 Petr 不会跳过几天，并且每天都会尽可能多地阅读，请确定他将在一周中的哪一天阅读本书的最后一页。

输入格式

第一行包含单个整数 n(1≤n≤1000) — 书中的页数。

第二行包含七个不超过 1000 的以空格分隔的非负整数——这些整数表示 Petr 在周一、周二、周三、周四、周五、周六和周日可以阅读的页数。 保证这些数字中至少有一个大于零。

输出格式

打印一个数字——，etr 读完这本书的星期几。 一周中的天数按自然顺序从一个开始编号：周一、周二、周三、周四、周五、周六、周日。

输入输出样例

输入

100 15 20 20 15 10 30 45

输出

6

说明

无

#include<bits/stdc++.h>
using namespace std;int a[10];int main()
{int total;scanf("%d",&total);for(int i=0;i<7;i++)	scanf("%d",&a[i]);int sum=0;int ans=0;while(sum<total){for(int i=0;i<7;i++){sum+=a[i];if(sum>=total)	{ans=i+1;break;}}}printf("%d\n",ans);return 0;
}

循环＋数组模拟可以解决这道题目 

---

第3题

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1−5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 j 件物品的价格为 v[j]，重要度为 w[j]，共选中了 k 件物品，编号依次为 j1​,j2​,…,jk​，则所求的总和为：

v[j1​]×w[j1​]+v[j2​]×w[j2​]+…+v[jk​]×w[jk​]。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为 2 个正整数，用一个空格隔开：n,m（其中 N(<30000) 表示总钱数，m(<25) 为希望购买物品的个数。）

从第 2 行到第 m+1 行，第 j 行给出了编号为 j−1 的物品的基本数据，每行有 2 个非负整数 v p（其中 v 表示该物品的价格(v≤10000)，p 表示该物品的重要度(1−5)。

输出格式

1 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。

输入输出样例

输入 1

1. 1000 5
2. 800 2
3. 400 5
4. 300 5
5. 400 3
6. 200 2

输出 1

1. 3900

输入 1000，表示总钱数，5 为希望购买物品的个数，随后 5 行，先给出物品的价格为 800，再列出重要度为 2。

计算方式为：

1. 先求得总收获，为重要度\*价格，即 800 \* 2 = 1600，400 \*5=20000，300 \* 5=1500，400 \* 3=1200，200 \* 2=400。
2. 根据 01 背包进行计算，f[j]=max(f[j],f[j−v[i]]+w[i])，v[i] 为价值，w[i] 为总收获。代入计算求得最大价值。
3. 最后输出 f[m]，背包大小为 m 时最大值

【来源】

NOIP 2006 普及组 第二题

#include<bits/stdc++.h>
using namespace std;const int N=30000+10;
int f[N];int main()
{int n,m;scanf("%d%d",&m,&n);for(int i=0;i<n;i++){int v,w;scanf("%d%d",&v,&w);for(int j=m;j>=v;j--){f[j]=max(f[j],f[j-v]+v*w);}}printf("%d\n",f[m]);return 0;
}

 是一个01背包问题

不能超过的钱数相当于背包容量

每一件物品的价格相当于物品的体积

价格乘以重要度相当于物品的价值价值

经过上述等价变形，就完全转换为了01背包问题，注意第二层循环从最大容量开始减小

01背包的方程如下

f[j]=max(f[j],f[j-v[i]]+w[i]);