首页 > 代码库 > Light oj 1100 - Again Array Queries (鸽巢原理+暴力)
Light oj 1100 - Again Array Queries (鸽巢原理+暴力)
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1100
给你n个数，数的范围是1~1000，给你q个询问，每个询问问你l到r之间数的最小差是多少。
要是l到r的数字个数大于1000，必定会有两个数字重复，所以此时最小差就为0。要是小于等于1000就直接暴力即可。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 const int N = 1e5 + 5;16 int a[N], cnt[1001];17 18 int main()19 {20 int t, n, q, l, r;21 scanf("%d", &t);22 for(int ca = 1; ca <= t; ++ca) {23 scanf("%d %d", &n, &q);24 for(int i = 0; i < n; ++i) {25 scanf("%d", a + i);26 }27 printf("Case %d:\n", ca);28 while(q--) {29 scanf("%d %d", &l, &r);30 if(r - l + 1 > 1000) {31 printf("%d\n", 0);32 } else {33 for(int i = l; i <= r; ++i) {34 ++cnt[a[i]];35 }36 int ans = 1001, lpos = -1001;37 for(int i = 1; i <= 1000; ++i) {38 if(cnt[i] > 1) {39 ans = 0;40 break;41 } else if(cnt[i]) {42 ans = min(ans, i - lpos);43 lpos = i;44 }45 }46 for(int i = l; i <= r; ++i) {47 cnt[a[i]] = 0;48 }49 printf("%d\n", ans);50 }51 }52 }53 return 0;54 }
Light oj 1100 - Again Array Queries (鸽巢原理+暴力)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。