Peter算法小课堂—前缀和数组的应用

桶

相当于计数排序，看一个视频

桶排序

太戈编程1620题

算法解析

#include <bits/stdc++.h>
using namespace std;
const int R=11;
int cnt[R];//cnt[t]代表第t天新增几人 
int s[R];//s[]数组是cnt[]数组的前缀和数组 
int n,t;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>t;cnt[t]++;}for(int k=1;k<=10;k++)s[k]=s[k-1]+cnt[k];//s[t]代表前t天累计几人 for(int k=1;k<=10;k++)cout<<s[k]<<" ";cout<<endl;return 0;
}

重要的地方已经标注好了

太戈编程第1621题

cin>>n;
for(int i=1;i<=n;i++){string s;int t,x;cin>>s>>t>>x;cnt[t]+=x;
}
int ans=*max_element(cnt+1,cnt+301);
cout<<ans<<endl;

太戈编程第1622题

cin>>n>>m;
for(int i=1;i<=n;i++){cin>>x;cnt[x]++;
}
for(int k=1;k<=100;k++)s[k]=s[k-1]+cnt[k];
for(int i=1;i<=m;i++){cin>>x;cout<<n-s[x-1]<<" ";
}
cout<<endl;

希望对大家有用，三联必回