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] = 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分)