Together
题目描述
You are given an integer sequence of length N, a1,a2,…,aN.For each 1≤i≤N, you have three choices: add 1 to ai, subtract 1 from ai or do nothing.
After these operations, you select an integer X and count the number of i such that ai=X.
Maximize this count by making optimal choices.
Constraints
1≤N≤105
0≤ai<105(1≤i≤N)
ai is an integer.
输入
The input is given from Standard Input in the following format:N
a1 a2 .. aN
输出
Print the maximum possible number of i such that ai=X.样例输入 Copy
7 3 1 4 1 5 9 2
样例输出 Copy
4
提示
For example, turn the sequence into 2,2,3,2,6,9,2 and select X=2 to obtain 4, the maximum possible count. 没啥好说的，题目怎么说怎么做#include<iostream>
#include<map>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]++;
}
int res,maxn=-1;
for(int i=1;i<=n;i++)
{
res=b[a[i]]+b[a[i]-1]+b[a[i]+1];
maxn=max(maxn,res);
}
cout<<maxn<<endl;
return 0;
}
Derangement
题目描述
You are given a permutation p1,p2,…,pN consisting of 1,2,..,N. You can perform the following operation any number of times (possibly zero):Operation: Swap two adjacent elements in the permutation.
You want to have pi≠i for all 1≤i≤N. Find the minimum required number of operations to achieve this.
Constraints
2≤N≤105
p1,p2,..,pN is a permutation of 1,2,..,N.
输入
The input is given from Standard Input in the following format:N
p1 p2 .. pN
输出
Print the minimum required number of operations样例输入 Copy
5 1 4 3 5 2
样例输出 Copy
2
提示
Swap 1 and 4, then swap 1 and 3. p is now 4,3,1,5,2 and satisfies the condition. This is the minimum possible number, so the answer is 2. 相邻的，看一眼数据范围不能用冒泡 然后以为是模拟，就开始模拟了，模拟过程中发现这是个思维题#include<iostream>
#include<map>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int t=0;
for(int i=1;i<=n;i++)
{
if(a[i]==i&&a[i+1]==i+1)
{
t++;
swap(a[i],a[i+1]);
}
if(a[i]==i&&a[i]!=i+1)
{
t++;
swap(a[i],a[i+1]);
}
}
cout<<t<<endl;
return 0;
}
/*那一个位置只能有一个数字不可以
1 2 4 5--->一次
3 2 5 4--->
能交换之后再不匹配的只能是 2 3 1 5
那这本身就不需要交换啊
1 3 2
*/
问题 B: 比例简化
题目描述
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498人，反对的有902人，那么赞同与反对的比例可以简单的记为1498:902。不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
现给出支持人数A，反对人数B，以及一个上限L，请你将A比B化简为A’比B’，要求在A’和B’均不大于L且A’和B’互质（两个整数的最大公约数是1）的前提下，A’/B’≥A/B且A’/B’-A/B的值尽可能小。
输入
输入共一行，包含三个整数A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。1≤A≤1,000,000，1≤B≤1,000,000，1≤L≤100，A/B≤L。输出
输出共一行，包含两个整数A’，B’，中间用一个空格隔开，表示化简后的比例。样例输入 Copy
1498 902 10
样例输出 Copy
5 3
枚举就行
#include<iostream>
using namespace std;
int gcd(int n,int m)
{
if(n%m==0) return m;
else return gcd(m,n%m);
}
int main(){
double a,b,l;
cin>>a>>b>>l;
double x,y,minn=100000,i,j,d,f1,f2;
x=a/b*1.0;
//cout<<x<<endl;
for(double i=1;i<=l;i++)
{
for(double j=1;j<=l;j++)
{
y=i/j*1.0;
if(gcd(i,j)==1&&y>=x)
{
d=y-x;
if(minn>d)
{
minn=d;
f1=i;
f2=j;
}
}
}
}
cout<<f1<<" "<<f2<<endl;
return 0;
}
问题 A: 珠心算测验
题目描述
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？ 最近老师出了一些测验题，请你帮忙求出答案。输入
输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。 第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。3<=n<=100,给出的正整数大小不超过10000输出
输出共一行，包含一个整数，表示测验题答案。样例输入 Copy
4 1 2 3 4
样例输出 Copy
2
提示
由1+2=3，1+3=4，故满足测试要求的答案为2。注意，加数和被加数必须是集合中的两个不同的数。
#include<iostream>
using namespace std;
const int N=110;
int a[N];
int b[100010];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]++;
}
int t=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&b[a[i]+a[j]]!=0)
{
t++;
b[a[i]+a[j]]=0;
}
}
}
cout<<t<<endl;
return 0;
}