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;
}

---