ABC296 CDE 题解 - chenyining

chenyining 2023-06-29 7:55:15 2023-07-06 12:18:56 11

C题

题意:

数据范围:

思路:

时间复杂度:

#include<bits/stdc++.h>
using namespace std;

int n;
int a[200010];
int find(int x){
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(a[mid]==x)//如果找到了就return 1,表示找到了
			return 1;
		else if(a[mid]<x)
			l=mid+1;
		else 
			r=mid-1;
	}
	return 0;
} 
int main(){
  	int x;
	cin>>n>>x;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);//排序完才能二分
	for(int i=1;i<=n;i++){
		if(find(a[i]+x)){
			cout<<"Yes";
			return 0;
		}
	} 
	cout<<"No";
    return 0;
}

D题

题意:

数据范围:

思路1:

思路2:

退

时间复杂度:

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	int n,m;
	cin>>n>>m;
	int mi=1e18;
	for(int a=1;a<=n;a++){
		int b=ceil(m*1.0/a);		
		if(b<=n){
			if(a*b<mi)
				mi=a*b;
		}
		if(a>b)
			break;
	}
	if(mi==1e18)
		cout<<-1;
	else 
		cout<<mi;
    return 0;
}

E题

题意:

数据范围:

思路:

时间复杂度:

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

int a[200010],d[200010],n;
queue<int>q;
vector<int>v[200010];
void sort(){
   	for(int i=1;i<=n;i++)
   		if(!d[i])q.push(i);
   	while(!q.empty()){
      	int x=q.front();
      	q.pop();
      	for(auto y:v[x]){
      		d[y]--;
         	if(d[y]==0)q.push(y);
      	}
   	}
}
int main(){
	cin>>n;	
   	for(int i=1;i<=n;i++){
      	cin>>a[i];
      	v[i].push_back(a[i]);
      	d[a[i]]++;
   	}
   	sort();
	int ret=0;
   	for(int i=1;i<=n;i++){
      	if(d[i])ret++;
   	}
   	cout<<ret; 
   	return 0;
} 
{{ vote && vote.total.up }}

共 1 条回复

cookiebus

不错不错!