Codeforces Round #543 (Div. 2)B,C

B

题意

给你n(<=1000)个数a[i](<1e5),找出最多对和相等的数，每个数只能用一次，且每个数保证各不相同

题解

重点：每个数只会出现一次
枚举所有数对的和并标记，遍历和，次数最多即答案
为什么这样可以保证没有数使用了两次？

因为每个数只会出现一次，所以对于某个和来说，组成的每个数对都是唯一的

代码

#include<bits/stdc++.h>

using namespace std;

int n,i,a[1005],j,ans,vi[200005];

int main(){

	cin>>n;

	for(i=1;i<=n;i++){

		cin>>a[i];

	}

	for(i=1;i<=n;i++){

		for(j=i+1;j<=n;j++){

			vi[a[i]+a[j]]++;

		}

	}

	for(i=1;i<=200000;i++)

		ans=max(ans,vi[i]);

	cout<<ans;

}

C

题意（阅读题，难在题意和实现细节）

模拟判题系统，一共有n(<=1000)个提交，每个提交有a[i](<=150)个数据点，有k(<=100)个判题机器，判题顺序如下：n个提交依次判定，假如有空闲的机器就将下一个提交放上去，判定一个数据点需要1s，直到所有提交判定完毕。

定义d为判题率为round(100*m/n),m为已经判定完的提交数，对于每个提交来说，假如存在一个时刻，提交正在判定第x个数据点，而此时的d也是x，问有多少个这样的提交？

题解

数据量较少，所以直接模拟即可
每次模拟的是+0.5的情况，因此需要操作顺序为:将每个数据点+1，统计上一秒末的完成度->结算本秒->更新完成情况

坑点

对于有的提交，可能会多次满足条件，导致重复计算结果，所以需要标记每个提交

代码

#include<bits/stdc++.h>

using namespace std;

int n,k,m,a[1005],i,p[1005],j,vi[1005],d,ans,mk[1005];

double ti=0.5;

int main(){

	cin>>n>>k;

	for(i=1;i<=n;i++){

		cin>>a[i];

	}

	k=min(n,k);

	for(i=1;i<=k;i++)vi[i]=1;

	for(;;ti+=1){

		for(i=1;i<=n;i++){

			if(vi[i]==1)p[i]++;

		}

        d=round(100.0*m/n);

        /*for(i=1;i<=n;i++)cout<<p[i]<<" ";

        cout<<d<<" ";*/

		for(i=1;i<=n;i++){

			if(vi[i]==1&&p[i]==d&&!mk[i]){ans++;mk[i]=1;}

		}

        //out<<ans<<" "<<ti<<endl;

        for(i=1;i<=n;i++){

			if(p[i]==a[i]&&vi[i]==1){

				m++;vi[i]=2;

				for(j=i+1;j<=n;j++){

					if(!vi[j]){vi[j]=1;break;}

				}

			}

		}	

		if(m==n)break;

	}

	cout<<ans;

}

巴特西

Codeforces Round #543 (Div. 2)B,C

B

C

最新文章

热门文章