C50-综合练习

一、有趣的桶排序

排序的思想-可视化

本质上是通过计数进行的排序

#include<iostream>
using namespace std;
int b[1005],n,t;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t;
        b[t]++;
    }
    for(int i=1000;i>=0;i--){
        while(b[i]--){
            cout<<i<<" ";
        }
    }
    return 0;
}

二、前缀和计算区间和

⭕️水壶的问题

方法1：枚举

#include<iostream>
using namespace std;
int n,k;
int a[10005]={};
int main(){
    cin >> n >> k;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i=1; i<=n-k; i++){
        int sum = 0;
        for (int j=i; j<=i+k; j++){
             sum += a[j];
        }  
        ans = max(ans, sum);
    }
    cout << ans;
    
    return 0;
}

方法2：前缀和

#include<iostream>
using namespace std;
int a[10005],sum[10005];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=a[i]+sum[i-1];
	} 
	int max=0;
	for(int i=k+1;i<=n;i++){
		int res=sum[i]-sum[i-k-1];
		if(res>max)
			max=res;
	}
	cout<<max;
	return 0;
}

⭕️左邻右舍

考虑到首、尾以及中间的常规情况即可。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,n;
    cin>>a>>n;
    if(n==1){
        cout << 2 << " " << a;
    }
    else if(a==n){
        cout << 1 << " " << n-1;
    }
    else{
        cout << n-1 << " " << n+1;
    }
	return 0;
}

⭕️字符串

获取字符串的实际长度， s.size() 或者s.length()

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int len = s.length() - 1;

	cout<<s; 
    for(int i=len; i>=0;i--){
        cout<<s[i];
    }
    return 0;
}

三、作业练习

团队 -> 竞赛。补题完成剩下的2道编程题。