T1 走楼梯
题目：
是一道简单的dp题，可以压缩成一维数组。
#include <iostream>
using namespace std;
int main()
{
long long int n,a[55];
cin>>n;
a[0]=1,a[1]=1,a[2]=2;
for(int i=3;i<=50;i++){
if(i<=5) a[i]=a[i-1]+a[i-2];
else a[i]=a[i-1]+a[i-3]+a[i-5];
}
cout<<a[n];
return 0;
}T2 走路
题目：
也是一道dp题
#include <iostream>
using namespace std;
int n,m,a[105],b[105],dp[105][100005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j-a[i]>=0){
dp[i][j] |= dp[i-1][j-a[i]];
}
if(j-b[i]>=0){
dp[i][j] |= dp[i-1][j-b[i]];
}
}
}
for(int i=0;i<=m;i++)
cout<<dp[n][i];
return 0;
}T3 订单编号
题目：
样例：
可以用并查集存x对应的最小的编号。（这里用unordered_map 才能过 是可能会被卡的O(1),map复杂度是lO（logn）,对排序没有什么需求时可以用unordered_map）
#include <bits/stdc++.h>
using namespace std;
int a[10000005],n;
unordered_map <int,int> f;
int find(int x){
if(f[x]==0) f[x]=x;
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
void merge(int x,int y){
x=find(x);
y=find(y);
f[x]=y;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
cout<<find(a[i])<<' ';
merge(a[i],f[a[i]]+1);
}
return 0;
}T5 饿饿 饭饭
题目：
样例：
设最多可以打x轮，然后减去x-1轮后的情况，对最后一轮进行模拟即可。（求轮数x应该用二分去做）
#include <iostream>
using namespace std;
long long int n,k,a[100005],tot,sum,ans[100005];
bool check(int x){
long long int p=0;
for(int i=1;i<=n;i++){
p += (a[i]>=x ? x : a[i]);
}
if(p<=k) return true;
else return false;
}//计算出能打x轮
void calc(int x){
sum=0;
for(int i=1;i<=n;i++){
sum +=(a[i]>=x ? x : a[i]);
a[i] -= x;//减去l轮的饭量
}
}
void prework(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
tot+=a[i];//学生总饭量
}
}
void solve(){
int l=0,r=2e9,mid;
while(l+1<r){
mid = (l+r)/2;
if(check(mid)){
l = mid;
}
else r = mid;
}//此时l为最后一轮前一轮的轮数
calc(l);
k-=sum;//剩余的打饭量
//进行最后一轮的打饭
int stop;
int cnt=1;
for(int i=1;i<=n;i++){
if(k==0){
stop = i;
break;
//打完了
}
if(a[i]>1){
ans[cnt] = i;
cnt++;
k--;
}
else if(a[i]==1){
k--;
}
}
//cout<<l<<endl<<k<<endl<<stop<<endl;
for(int i=stop;i<=n;i++){
if(a[i]>=1){
cout<<i<<' ';
}
}
for(int i=1;i<cnt;i++) cout<<ans[i]<<" ";
}
int main(){
prework();
if(tot<k){
cout<<"-1";
return 0;
}
if(tot==k) return 0;
solve();
return 0;
}