8.02-河东-401

T639114 大楼

求从左往右最左边的比最左边大的数的下标。因为数据说 $N<=100$ 我们直接从左到右枚举就行了。

#include<bits/stdc++.h>
using namespace std;
int n,y;
signed main(){
	cin>>n;
	cin>>y;
	for(int i=2;i<=n;++i){
		int x;
		cin>>x;
		if(x>y){
			cout<<i<<"\n";
			return 0;
		}
	}
	cout<<-1<<"\n";
	return 0;
} 

T639104 信奥大联赛

要我们求出编号为所有人总分取模 $N$ 的用户名

先边输入边计算总分，最后直接 $%N$。再给用户按字典序从小到大排序因为题目说是从 $0$ 开始的，所以编号为 $i-1$。最后判断如果编号等于我们之前求出来的书，就直接输出用户名。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct node{
	string s;
	int t,u;
}a[N];
int n;
bool cmp(node x,node y){
	return x.s<y.s;
}
int sum;
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].s>>a[i].t;
		sum+=a[i].t;
	}
	sum%=n;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){
		a[i].u=i-1;
		if(a[i].u==sum){
			cout<<a[i].s<<"\n";
		}
	}
	
	return 0;
}

T638475 调酒大师

这道题有很多种写法

二分

直接暴力的话可能不能 $AC$，只要一个简单的二分就可以降低时间复杂度 $AC$。

我们先套上二分的模版，$l$ 初始值为 $-1$，因为有可能连一杯酒也挑不出来的情况。$r$ 要等于 $min(n,m)+1$，因为可以调的酒的份数最多也是一个 $n$ 或 $m$ 的值，然而如果选择了大的那个数，而另一个数因为一杯酒要 $4$ 个，所以要 $÷3$，因此不成立。

然后 $check$，这个更简单，我们找一下规律：

从以上列表中我们可以发现，酒的份数 $×4$（果汁和白酒总数的最大值）一定要大于或刚好等于果汁 $+$ 白酒 (也就是$n+m$)。

对于 100% 的数据，保证 $0≤n,m≤10^9 ，1≤T≤10^4$

1e9+1e9 可能报 $int$，记得开个 $long$ $long$

#include<bits/stdc++.h>
using namespace std;
#define int long long //不开 long long 见祖宗
int T;
int n,m;
bool check(int x){
	return (n+m)>=4*x;
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		int l=-1,r=min(n,m)+1;
		while(l+1<r){
			int mid=(l+r)/2;
			if(check(mid)){
				l=mid;
			}
			else r=mid;
		}
		cout<<l<<"\n";
	}
	return 0;
}

找规律

这道题我们可以直接输出答案，因为题目并没有让我们输出方案，只是然我们输出答案。

只要观察下答案就会发现，所有答案只有两种方案。

第一种是 $(n+m)/4$ ，这种方案是 $2+2$，两个白酒，两个果汁的方案。

第二种是 $min(n,m)$ ，这种方案是 $3+1$ 或 $1+3$，我们可以看做两个数的最小值。

最后去两种方案的最小值，因为如果有一个大于另一个时，大的那个其实是不正确的一种方案，正确的应该是两个都是一样的。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int T;
signed main(){
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		cout<<min((n+m)/4,min(n,m))<<"\n";
	}
	return 0;
}