RE20分为啥

常规
1

image
image814×569 19.4 KB

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int,int> a;
map<int,int> f;
int n,x;
signed main(){
 	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],f[a[i]]++;
	while(cin>>x){
		cout<<f[x]<<" ";
	}
}
//map<int,int>::iterator it;
//for(it=mp.begin();it!=mp.end();it++)
//	cout<<it->first<<" "<<it->second<<"\n";
2

二分写

3

用二分查找写

4

思路：

1.按照题目要求输入数据，存储到数组中去,

2.开始二分查找，二分查找进行下去的关键条件：l<=r

二分查找核心代码：

while (l<= r) {
    mid = (l + r) / 2;
    if (a[mid] < m) {
        l = mid + 1;
    }else{
        r = mid - 1;
    }
}

找完之后记得判断是否有m，没有则直接输出0，有的话则在第一次二分查找结束后记录m出现左边界的位置p1

再通过第二次二分查找记录m出现右边界的位置p2，p2-p1即是m出现的个数

根据以上思路，我们就可以完成本题
伪代码：

#include<bits/stdc++.h>
using namespace std;
int a[?];//定义数组
int main()
{
    int ?;
    cin>>?;
    for(int i=1;i<=?;i++)
        cin>>a[i];
    int ?;
    while(?)
    {
        int l =1, r = ?, count = 0;
        while(l <= r)
        {
            int mid = (l+r) / 2;//查找
            if(a[mid] == m)
            {
                count++;
                int ? = mid - 1;
                while(?>= l && a[?] == m)
                {
                    count++;
                    ?--;
                }
                ? = mid + 1;
                while(? <= r && a[temp] == m)
                {
                    count++;
                    ?++;
                }
                break;
            }
            else if(a[mid] < m)
                l = mid + 1;
            else
                r = mid - 1;
        }
        cout << count << " ";
    }
    return 0;
}
5

给个解决方案