【错题集】ruby 和薯条(排序 + 二分 / 双指针)
创始人
2025-01-08 11:05:30
0次

牛客对应题目链接:ruby和薯条 (nowcoder.com)


一、分析题目

1、解法一:排序 + 二分。

先排序,然后枚举较⼤值,在 [1, i - 1] 区间找差值的左右端点即可。

2、解法二:排序 + 前缀和 + 双指针。

  • 先排序;
  • 求差值在 [L, R] 区间内数对的个数,可以转化成求 [0, R] 区间内的个数 - [0, L] 区间内的个数。
  • 其中求 [0, X] 区间内数对的个数,可以用双指针快速统计出以 arr[right] 为结尾的数对有多少个。

二、代码

// 修改过后的代码 #include  #include  using namespace std;  typedef long long LL; int n, l, r; const int N=2e5+10; int a[N];  LL s(int x) {     LL res=0;     int left=0, right=0;     while(rightx) left++;         res+=right-left;         right++;     }     return res; }  int main() {     cin >> n >> l >> r;     for(int i=0; i> a[i];     sort(a, a+n);     cout << s(r)-s(l-1) << endl;     return 0; }
// 推荐解法一:排序 + 前缀和 + 滑动窗⼝ #include  #include   using namespace std;  const int N = 2e5 + 10; int n, l, r; int arr[N];  // 找出差值在 [0, x] 之间⼀共有多少对 long long find(int x) {     int left = 0, right = 0;     long long ret = 0;     while(right < n)     {         while(arr[right] - arr[left] > x) left++;         ret += right - left;         right++;     }       return ret; }  int main() {     cin >> n >> l >> r;     for(int i = 0; i < n; i++) cin >> arr[i];     sort(arr, arr + n);       cout << find(r) - find(l - 1) << endl;       return 0; }  //解法二:排序 + ⼆分 #include  #include   using namespace std;  const int N = 2e5 + 10; int n, l, r; int arr[N];  int main() {     cin >> n >> l >> r;     for(int i = 1; i <= n; i++) cin >> arr[i];     sort(arr + 1, arr + n + 1);       long long ret = 0;     for(int i = 2; i <= n; i++)     {         int L, R;         // 找左端点         int left = 1, right = i - 1;         while(left < right)         {             int mid = (left + right) / 2;             if(arr[mid] >= arr[i] - r) right = mid;             else left = mid + 1;         }         if(arr[left] >= arr[i] - r) L = left;         else L = left + 1;         // 找右端点         left = 1, right = i - 1;         while(left < right)         {             int mid = (left + right + 1) / 2;             if(arr[mid] <= arr[i] - l) left = mid;             else right = mid - 1;         }         if(arr[left] <= arr[i] - l) R = left;         else R = left - 1;           if(R >= L) ret += R - L + 1;     }       cout << ret << endl;       return 0; }

三、反思与改进

双指针部分思路繁琐了,还有就是求前缀和的函数返回值的类型忘记修改为 long long 了...

相关内容

热门资讯

交流学习经验辅助器!毛豆娱乐辅... 交流学习经验辅助器!毛豆娱乐辅助器多功能AI脚本,毛豆娱乐一贯是有辅助器脚本1、毛豆娱乐辅助软件下载...
玩家必备教程辅助!九游互娱辅助... 玩家必备教程辅助!九游互娱辅助多功能AI攻略,九游互娱本来真的是有辅助攻略1、在九游互娱插件功能辅助...
玩家必备科普外挂!新天地外挂多... 玩家必备科普外挂!新天地外挂多功能AI技巧,新天地本来真的有外挂技巧1、起透看视 新天地辅助软件价格...
揭秘真相作弊器!长盈互娱作弊器... 揭秘真相作弊器!长盈互娱作弊器多功能AI软件,长盈互娱一贯是真的有作弊器软件1、任何长盈互娱透视是真...
教学盘点辅助!四通娱乐3辅助多... 教学盘点辅助!四通娱乐3辅助多功能AIapp,四通娱乐3本来有辅助app亲,关键说明,四通娱乐3透视...
必备攻略外挂!千秋互娱外挂多功... 必备攻略外挂!千秋互娱外挂多功能AI工具,千秋互娱一直真的是有外挂工具1、玩家可以在千秋互娱透视最简...
推荐攻略开挂!七天娱乐开挂多功... 推荐攻略开挂!七天娱乐开挂多功能AIapp,七天娱乐真是存在有开挂app1、推荐攻略开挂!七天娱乐开...
记者发布透视挂!大大娱乐透视挂... 记者发布透视挂!大大娱乐透视挂多功能AI方法,大大娱乐切实真的是有透视挂方法1、玩家可以在大大娱乐透...
一分钟了解透视器!新九五透视器... 一分钟了解透视器!新九五透视器多功能AI脚本,新九五都是存在有透视器脚本进入游戏-大厅左侧-新手福利...
总算了解外挂!嘻嘻娱乐外挂多功... 总算了解外挂!嘻嘻娱乐外挂多功能AI脚本,嘻嘻娱乐一贯是有外挂脚本1、每一步都需要思考,不同水平的挑...