比赛 EYOI与SBOI开学欢乐赛12th 评测结果 AAAAWWWWWW
题目名称 坐标压缩 最终得分 40
用户昵称 op_组撒头屯 运行时间 1.429 s
代码语言 C++ 内存使用 7.33 MiB
提交时间 2022-10-17 20:32:34
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000+5;
int n,s,cnt;
int a[N],b[N],c[N];
vector<int>v[N];
inline int read(){
	int tmp=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))tmp=(tmp<<3)+(tmp<<1)+(ch^48),ch=getchar();
	return tmp;
}
int main(){
	freopen ("coord.in","r",stdin);
	freopen ("coord.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&s);
		for (int i=1;i<=n;i++){
			a[i]=read(),b[i]=a[i];
			v[i].clear();
		}
		sort(b+1,b+n+1);
		cnt=unique(b+1,b+n+1)-b-1;
		ll t=0;
		for (int i=1;i<=n;i++){
			a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
			t+=a[i];v[a[i]].push_back(i);
		}
		if (t<=s) printf("%d\n",n+1);
		else printf("1\n");
	}
	return 0;
}