當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

洛谷 P3184 [USACO16DEC]Counting Haybales数草垛

發布時間：2023/11/29 编程问答 38 豆豆

生活随笔收集整理的這篇文章主要介紹了洛谷 P3184 [USACO16DEC]Counting Haybales数草垛小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

　　　洛谷 P3184 [USACO16DEC]Counting Haybales數草垛

題目描述

Farmer John has just arranged his? $\leq N \leq 100,0001≤N≤100,000?) at various points along the one-dimensional road running across his farm. To make sure they are spaced out appropriately, please help him answer?QQ?queries (1 \leq Q \leq 100,0001≤Q≤100,000?), each asking for the number of haybales within a specific interval along the road.$

農夫John在一條穿過他的農場的路上（直線）放了N個干草垛（1<=N<=100,000），每個干草垛都在不同的點上。為了讓每個干草垛之間都隔著一定的距離，請你回答農夫John的Q個問題（1<=Q<=100,000），每個問題都會給出一個范圍，詢問在這個范圍內有多少個干草垛。

（其實就是有一條數軸上有N個不重復的點，再問Q個問題，每個問題是給出一個范圍，問此范圍內有多少個點？）

（在給出范圍的邊界上也算）

輸入輸出格式

輸入格式：

The first line contains?

The next line contains? $\ldots 1,000,000,0000…1,000,000,000?, indicating that there is a haybale at each of those locations.$

Each of the next? $\leq A \leq B \leq 1,000,000,0000≤A≤B≤1,000,000,000?) giving a query for the number of haybales between?AA?and?BB?, inclusive.$

第一行包括N和Q

第二行有N個數字，每個數字的范圍在0~1,000,000,000，表示此位置有一個干草垛。

接下來的Q行，每行包括兩個數字，A和B（0<=A<=B<=1,000,000,000）表示每個詢問的范圍

輸出格式：

You should write?

總共Q行，每行輸出此范圍內的干草垛數量

輸入輸出樣例

輸入樣例#1：?復制 4 6 3 2 7 5 2 3 2 4 2 5 2 7 4 6 8 10 輸出樣例#1：?復制 2 2 3 4 1 0

思路：區間求和? ? ? ? ? ? ? ? ? ? ? ? ? ??難度：普及/提高-?

暴力：線段樹。只能過一個點，因為測試數據太大（10⁹），而線段樹最多能開到10⁷

#include<cstdio> #define N 10000005 using namespace std; int n, m, x, y; struct nond {int ll, rr;int sum; }tree[4*N]; void up(int now) {tree[now].sum = tree[now*2].sum+tree[now*2+1].sum; } void build(int now, int l, int r) {tree[now].ll = l; tree[now].rr = r;if(l == r) {tree[now].sum = 0;return ;}int mid = (l+r) / 2;build(now*2, l, mid);build(now*2+1, mid+1, r);up(now); } void change(int now, int s) {if(tree[now].ll == tree[now].rr) {tree[now].sum ++;return ;}int mid = (tree[now].ll+tree[now].rr) / 2;if(s<=mid) change(now*2, s);else change(now*2+1, s);up(now); } int query(int now, int l, int r) {if(tree[now].ll==l && tree[now].rr==r) {return tree[now].sum;}int mid = (tree[now].ll+tree[now].rr) / 2;if(l<=mid && mid<r) return query(now*2, l, mid) + query(now*2+1, mid+1, r);else if(r<=mid) return query(now*2, l, r);else return query(now*2+1, l, r); } int main() {int a[100005] = {0}, maxn = -1;scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);if(a[i] > maxn) maxn = a[i];}build(1, 1, maxn);for(int i = 1; i <= n; i++) change(1, a[i]);for(int i = 1; i <= m; i++) {scanf("%d%d", &x, &y);if(x > maxn) { printf("0\n"); continue; }printf("%d\n", query(1, x, y));}return 0; } 線段樹代碼

正解：運用 c++中的 lower_bound、upper_bound?

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 100010 using namespace std; int n, m, q, tot; int pos[MAXN], hash[MAXN]; int main() {scanf("%d%d", &n, &q);for(int i = 1; i <= n; i++) scanf("%d", &pos[i]);sort(pos+1, pos+1+n);for(int i = 1; i <= q; i++) {int x, y; scanf("%d%d", &x, &y);cout << upper_bound(pos+1, pos+n+1, y) - lower_bound(pos+1, pos+n+1, x) << ‘\n’;}return 0; } AC

PS：lower_bound(val) ：返回容器中第一個值大于等于val 的元素的 iterator 位置

? ? ? ? ?upper_bound(val) ：返回容器中第一個值大于val 的元素的 iterator 位置

轉載于:https://www.cnblogs.com/v-vip/p/8746161.html

總結

以上是生活随笔為你收集整理的洛谷 P3184 [USACO16DEC]Counting Haybales数草垛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。