关于这个练习11,部分题真心觉得很难,一方面是难在理解题目意思上,另一方面则是难在编写程序上。例如A题(乎乎的储蓄),刚开始我研究题意就花了一段时间,后来在编写程序上又犯了难,最后终于想到了一个绝佳的办法。
题目描述 :乎乎共有n个储蓄罐,编号从0到n-1。从第 1 天开始,乎乎每天都会往存钱罐里存钱。具体来说,第i天他会挑选一个存钱罐ai,并存入i元钱。过了d天后,他已经忘记每个储蓄罐里都存了多少钱了,你能帮帮他吗?
输入描述: 输入2行,第一行两个整数n,d; 第二行 d个整数,其中第i个整数为ai (保证0 ≤ ai ≤ n-1),每行的各个整数之间用单个空格分隔。保证1 ≤ n≤1,000; 1≤d≤1,000
输出描述: 输出n个用单个空格隔开的整数,其中第之个整数表示编号为i-1 的存钱罐中有多少钱 (i = 1...,N)。
AC代码:
#include<iostream> using namespace std; int main() { int i,a[1000]={0},d,n,num; cin>>n>>d; for(i=1;i<=d;i++) { cin>>num; a[num]+=i; } for(i=0;i<n-1;i++) { cout<<a[i]<<" "; } cout<<a[n-1]<<endl; return 0; }其实只要看懂题目,并将其转化成相应的程序表达出来,就可以了,完全就是逻辑上的合理表达。
还有另一种写法,看起来不一样,其实思路上完全相同:
#include <iostream> using namespace std; int main() { int n,d,i; cin>>n>>d; int a[1000]={0}; int m[1000]={0}; for (i=0;i<d;i++) { cin>>a[i]; } for (i=1;i<=d;i++) { m[a[i-1]]+=i; } for (i=0;i<n;i++) { cout<<m[i]<<" "; } return 0; }其余的题例如D题(统计数据),F题(谁是你的潜在朋友)等,也运用了类似的方法。
另外,练习中还有一些很重要的内容,如二分查找(H题)、I题(冒泡排序)、J题(选择排序),其中二分排序虽然用的次数不多,但作为一个很高效的排序方法,还是值得掌握的。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e3 + 5; int n, m; int a[N]; void binarySearch(int m) { int left = 0, right = n - 1; while (left <= right) { int mid = (left + right) / 2; if (a[mid] < m) { left = mid + 1; } else if (a[mid] > m) { right = mid - 1; } else { cout<<"YES"; break; } } if(left>right) cout << "NO" << endl; } int main() { cin >> n; for(int i = 0 ; i < n ; i++) { cin >>a[i]; } sort(a, a+n); cin >> m; binarySearch(m); return 0; }K题(开关门)、L题(校门外的树)虽然乍一看很难,但只不过是思路上比较巧妙,只要想明白其中道理,自然就能顺利AC
其余的题难度中等,只要将题目的意思正确用程序表达出来,就能AC。