题目链接
https://vjudge.net/contest/532113#problem/D
思考
虽然AC之后觉得题目难度不是很高,但也是第一次做比较综合的题目,花了快一天才做出来,只能说水平还是菜
思路
- 尝试直接暴力,会TLE
- 尝试优化
- TLE主要瓶颈在于第二层,因此需要优化第二层的时间复杂度为\(O(logn)\),将查找\(low\)、\(high\)的代码替换为二分查找
- 需要记录\(low-high\)之间的元素数,选择前缀和进行存储,方便查找
- 对于重复的元素可以用unorder_ed<int,int> map进行优化
代码
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
const int N=200010;
ll t,n,l,r,xin;
unordered_map<ll,ll> mm;
ll a[N],p[N];
int b_search1(int low,int high,ll x){
while (low<high)
{
int mid=low+high>>1;
if(a[mid]+x>=l) high=mid;
else low=mid+1;
}
return low;
}
int b_search2(int low,int high,ll x){
while (low<high)
{
// cout<<low<<' '<<high<<endl;
int mid=low+high>>1;
if(a[mid]+x>=r) high=mid;
else low=mid+1;
}
return low;
}
int main(){
io;
cin>>t;
while (t--)
{
mm.clear();
ll cnt=0,j=0;
cin>>n>>l>>r;
for (ll i = 1; i <= n; i++)
{
cin>>xin;
if(!mm.count(xin)){
a[++j]=xin;
}
mm[xin]++;
}
sort(a+1,a+j+1);
for (ll i = 1; i <= j; i++)
{
p[i]=p[i-1]+mm[a[i]];
}
for (ll i = 1; i < j; i++)
{
if(a[i]+a[i+1]>r||a[i]+a[j]<l) continue;
int low=b_search1(i+1,j,a[i]);
int high=b_search2(i+1,j,a[i]);
if(a[i]+a[high]>r) high--;
if(a[i]+a[low]<l) low++;
//这里需要注意
if(high>=low) cnt+=(p[high]-p[low-1])*mm[a[i]];
}
//最后对重复的元素进行判断
for (ll i = 1; i <= j; i++)
{
ll cnti=mm[a[i]];
if(cnti>=2&&2*a[i]>=l&&2*a[i]<=r){
cnt+=(cnti*(cnti-1))/2;
}
}
cout<<cnt<<endl;
}
return 0;
}
标签:532113D,int,ll,mid,high,算法,low,define,刷题
From: https://www.cnblogs.com/karson3/p/16949961.html