JHwong

用户名：dotcpp0724243

访问量：833

签　名：

等　　级
排　　名	3383
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

1435: 蓝桥杯历届试题-国王的烦恼
浏览：156

1427: 蓝桥杯2013年第四届真题-买不到的数目
浏览：39

2529: NOIP2012-同余方程-了解即可
浏览：34

你可能喜欢

老管家的忠诚

　　作者: JHwong　　　　发表时间：2024-01-11 23:02:10 浏览：32　|　评论：0　

原题链接：老管家的忠诚

# 老管家的忠诚度
## 思路解析
关注到本道题是典型的区间多次访问的题目的。所以，我们需要一种恰当的数据结构来帮助我们快速解决这个问题。如果采用的一般的方式方法一定会超时（显然是O(n^2)）。有许多快速查找的数据结构，这里我选取了线段树来完成。
##代码实现
```cpp
/* 
 * 题目 1305: 老管家的忠诚
 * this question, emmmm, maybe we shoule use the sagement tree to solve.becasue we can't alloc 100,000*100,000*4B size
 */
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX_NUMBER_OF_BILLS 100005
#define MAX_NUMBER_OF_QUERIES 100005

int number_of_bills, number_of_queries;
int billing_amount[MAX_NUMBER_OF_BILLS];

struct SagementTree {
  int left, right;
  int key;
} sagement_tree[MAX_NUMBER_OF_BILLS << 2];
#define left_queue(a) 2*(a)
#define right_queue(a) 2*(a) + 1
#define min(a, b) ( (a) < (b) ? (a) : (b) )
void createSagementTree(int idx, int left, int right) {
  if (left + 1 == right) {
	sagement_tree[idx].left = left, sagement_tree[idx].right = right;
	sagement_tree[idx].key = billing_amount[left];
	return;
  }
  int mid = left + (right - left) / 2;
  createSagementTree(left_queue(idx), left, mid);
  createSagementTree(right_queue(idx), mid, right);
  sagement_tree[idx].left = left; sagement_tree[idx].right = right;
  sagement_tree[idx].key = min(sagement_tree[left_queue(idx)].key, sagement_tree[right_queue(idx)].key);
  return;
}
int query(int idx, int left, int right) {
  if (left <= sagement_tree[idx].left && sagement_tree[idx].right <= right) return sagement_tree[idx].key;
  int min_left = 0x7FFFFFFF, min_right = 0x7FFFFFFF;
  if (left < sagement_tree[left_queue(idx)].right) min_left = query(left_queue(idx), left, right);
  if (sagement_tree[right_queue(idx)].left < right) min_right = query(right_queue(idx), left, right);
  return min(min_left, min_right);
}

inline int getint()                    //读入优化
{
  int a = 0; char x = getchar(); bool f = 0;
  while ((x < '0' || x>'9') && x != '-')x = getchar();
  if (x == '-')f = 1, x = getchar();
  while (x >= '0' && x <= '9')
  {
	a = a * 10 + x - '0'; x = getchar();
  }
  return f ? -a : a;
}
int main() {
  scanf("%d %d", &number_of_bills, &number_of_queries);
  for (int i = 0; i < number_of_bills; ++i) scanf("%d", billing_amount + i);
  createSagementTree(1, 0, number_of_bills);
  {
	int begin, end;
	for (int time_of_queries = 0; time_of_queries < number_of_queries; ++time_of_queries) {
	  begin = getint(), end = getint();
	  printf("%d ", query(1, begin - 1, end));
	}
  }
  return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

Hello, world! （Java代码）

交换Easy （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-求偶数和（C语言代码）

老管家的忠诚

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【金明的预算方案】（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

众数问题（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

Hello, world! （Java代码）

交换Easy （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

老管家的忠诚

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【金明的预算方案】 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C二级辅导-求偶数和（C语言代码）

　　评论区

【金明的预算方案】（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

众数问题（C语言代码）