admin 管理员组文章数量: 894193
C++题解:CSP迎国庆热身公益赛T2——猜数游戏(70分)
题目描述
小 W ⼜在数学课上睡着了!
作为惩罚,授课的数学⽼师 Wall_Breaker 强制小 W 要玩⼀个猜数游戏。
Wall_Breaker 会在⼀张纸上写下 N N N个值域在 [ 1 , M ] [1,M] [1,M] 的正整数 让小 W 猜,同时为了不过分地为难小 W ,他还会告诉小 W N − K + 1 N-K+1 N−K+1个数 ,其中 表示从第 i i i个数到第 i + K − 1 i+K-1 i+K−1个数中的最小值。
可是小 W 还是⼀如既往的蠢,即使提⽰到这样,他还是连⼀个数都猜不中。现在请你来好好激励他或教训他或鞭策他,告诉小 W 在已知信息下,最多能确定多少个位置上的数,他们⼜分别是多少?
输⼊描述
第⼀行三个正整数 N , K , M N,K,M N,K,M。
第二行 ( N − K + 1 ) (N-K+1) (N−K+1)个正整数 ,意义见题目描述。保证⾄少存在⼀个满⾜条件的 A A A数组。
输出描述
第⼀⾏输出⼀个⾮负整数 t o t tot tot ,表⽰最多能确定的 A i A_i Ai的个数。
接下来输出 t o t tot tot行,每行两个正整数 x , y x,y x,y,表⽰第 x x x个位置上的数可以确定是 y y y。
为了判题⽅便请按 递增的顺序输出每⼀组 ,且请勿重复输出相同的 x x x。
样例输入
4 2 10
8 9 8
样例输出
2
1 8
4 8
数据范围
在这里插入图片描述
算法思想(模拟)
本题给出了连续的 ( N − k + 1 ) (N - k + 1) (N−k+1)个区间,其中第 i i i个区间范围为 [ i , i + k − 1 ] [i,i+k-1] [i,i+k−1],以及每个的最小值 a i a_i ai,现在要确定的是i
位置上的值b[i]
,如下图所示:
通过上述信息,可以发现以下性质:
- 当 k = 1 k=1 k=1时,此时区间里只有一个数,即
b[i] = a[i]
,那么一共可以确定 ( N − k + 1 ) (N - k + 1) (N−k+1)个数。 - 如果 k ≠ 1 k\ne1 k=1,从第 i i i个遍历到第 i + 1 i+1 i+1区间时
- 如果 a i < a i + 1 a_i<a_{i+1} ai<ai+1,说明 b [ i ] b[i] b[i]就是区间 [ i , i + k − 1 ] [i,i+k-1] [i,i+k−1]的最小值,那么
b[i]=a[i]
。 - 如果 a i > a i + 1 a_i>a_{i+1} ai>ai+1,说明 b [ i + k ] b[i+k] b[i+k]就是区间 [ i + 1 , i + k ] [i + 1, i+k] [i+1,i+k]的最小值,那么
b[i+k]=a[i+1]
- 如果 a i = a i + 1 a_i=a_{i+1} ai=ai+1,那么无法确定。
- 如果 a i < a i + 1 a_i<a_{i+1} ai<ai+1,说明 b [ i ] b[i] b[i]就是区间 [ i , i + k − 1 ] [i,i+k-1] [i,i+k−1]的最小值,那么
特殊情况
如果a[i] = m
,那么b[i...i+k-1] = m
。
代码实现(70分)
这段代码只有70分,怀疑是a[i] = m
情况处理超时,暂时没想到优化方法Orz。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int a[N], b[N], p[N];
int main()
{int n, k, m;scanf("%d%d%d", &n, &k, &m);int t = n - k + 1;for(int i = 1; i <= t; i ++) scanf("%d", &a[i]);int res = 0;for(int i = 1; i < t; i ++){if(a[i] == m){int j = i, e = i + k - 1;while(j <= e) //TLE?{if(res == 0 || p[res - 1] != j){p[res] = j;b[res] = m;res ++;}j ++;}}//变大了if(a[i] < a[i + 1]){if(res == 0 || p[res - 1] != i){p[res] = i;b[res] = a[i];res ++;}}//变小了if(a[i] > a[i + 1]){if(res == 0 || p[res - 1] != i + k){p[res] = i + k;b[res] = a[i + 1];res ++;}}}printf("%d\n", res);for(int i = 0; i < res; i ++) printf("%d %d\n", p[i], b[i]);
}
本文标签: C题解CSP迎国庆热身公益赛T2猜数游戏(70分)
版权声明:本文标题:C++题解:CSP迎国庆热身公益赛T2——猜数游戏(70分) 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687603823h120100.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论