T1最小贪吃量

问题描述

问题描述 有N道菜，第i道菜的甜度为Ai，咸度为Bi。 小k可以按任意顺序排列这些菜，并按排列后的顺序依次尝。他会按照排列顺序吃菜，但一旦已吃菜品的总甜度超过X，或者总咸度超过Y，他就会停止进食。求他最终吃下的最少可能菜数。

约束条件

• $1≤N≤2×10^5$
• $1≤X,Y≤2×10^5×10^9$
• $1≤Ai,Bi≤10^9$
• 所有输入值均为整数。

解决方案

首先排序A,B并遍历累加求和，满足和>X或Y时的餐品数，最后取其最小值。

错误原因

部分变量没有开long long,总结为没有注意变量大小，下次要留意一下。

正确代码

#include<bits/stdc++.h>
using namespace std;
long long n,x,y;
long long s=0,v=0,q=0,w=0;
int main(){
	//freopen("eat.in","r",stdin);
	//freopen("eat.out","w",stdout);
	cin>>n>>x>>y;
	long long a[n],b[n];
	for(long long i=0;i<n;i++){
		cin>>a[i];
	}
	for(long long i=0;i<n;i++){
		cin>>b[i];
	}
	sort(a,a+n,greater<long long>());
	sort(b,b+n,greater<long long>());
	while(q<n&&s<=x)
		s+=a[q++];
	while(w<n&&v<=y)
		v+=b[w++];
	cout<<min(q,w);
	return 0;
}

T3倒立数对

问题描述

给定一个正整数N。求满足以下条件的正整数对(A,B)的数量（A和B都不大于N）：当A和B以十进制书写且没有前导零时，A的最后一位数字等于B的第一位数字，且A的第一位数字等于B的最后一位数字。

解决方案

首先枚举将所有小于等于n的整数并存为cnt[x][y],x为i的首位数字,y为i的末尾数字。则答案为c+=cnt[x][y] (1<=x,y<=9)。

正确代码

#include<bits/stdc++.h>
using namespace std;
int cnt[10][10];
int main(){
	//freopen("number.in","r",stdin);
	//freopen("number.out","w",stdout);
	int n,c=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x=i;
		while(x>=10){
			x/=10;
		}
		cnt[x][i%10]++;
	}
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			c+=cnt[i][j]*cnt[j][i];
		}
	}
	cout<<c;
	return 0;
}

注：所有freopen已注释