2023寒假模拟赛2题解(市赛)-创新互联

• • • 糖果
    • 班级的平均分
    • 宇宙裁缝
    • 据说这也是一道数学题？
    • 张经理的员工

可以知道购买三颗糖后的价格是n-x，则(n-x)/y为买完三颗后的糖的数量，要注意若n

#includeusing namespace std; 
int n,x,y;
int main(){cin>>n>>x>>y;
	if(ncout<<0;
	}else{cout<<3+(n-x)/y;
	}
	return 0;
}

for循环计算全部总数的和，然后除以班级人数5，得到平均数，注意因为使用小数，所以定义变量时要使用int，输出使用printf保留小数

#includeusing namespace std;
double a;
double b[10],c=0;
int main(){for(int i=0;i<5;i++){cin>>b[i];
		c+=b[i];
	}
	printf("%.1lf",c/5.0);
}

X形图案可以拆分成两根斜线，其中i=j时输出星号，或者i=n-i-1时输出星号即可，其他情况皆输出空格。
要注意最后不能输出行末空格，即在两个星号都输出后，不再输出空格

#includeusing namespace std;

int main() {int n;
    cin >>n;
    for(int i = 0; i< n; ++i) { for(int j = 0; j< n; ++j) { if(i == j)
                    printf("*");
             else if(j == n-i-1)
                    printf("*");
             else{		int p = max(i,n-i-1);
				if (j< p) printf(" ");
			}
         }
          printf("\n");
     }
    return 0;
}

如图所示
L 1 = L 3 + L 5 + L 7 L_1 = L_3 + L_5 + L_7 L1​=L3​+L5​+L7​
L 2 + L 6 = L 4 + L 8 L_2 + L_6 = L_4 + L_8 L2​+L6​=L4​+L8​
所以有：
L 1 + L 2 + . . . + L 8 = 2 ∗ ( L 1 + L 2 + L 6 ) = 40 L_1 + L_2 +...+ L_8 = 2 *(L_1 + L_2 + L_6) = 40 L1​+L2​+...+L8​=2∗(L1​+L2​+L6​)=40

解题思路
每种方案都给出了a、b两个聚集工位。在题目中，查询次数 q 大为1e5，所以在每次查询时间复杂度不能高于log级别，每次查询给出的a和b。

最短路径中有三种情况：
（一）、位于 a 左边的员工应该前往 a 。
（二）、位于 b 右边的员工应该前往 b 。
（三）、位于a、b之间的工位若相比于到 b 的距离，该工位距离 a 较近则前往 a ，否则前往 b 。

关键点：统计出每一个工位上的员工，并提取有用信息。
步骤一、预处理——方便快速查询出结果
①、数组Y记录每个工位上的员工人数，用下标来表示不同工位。
②、统计小于等于i位置的员工个数，记录在数组min_i。
③、统计小于等于i位置的员工下标之和，记录在数组min_i_sum。
④、统计大于等于i位置的员工个数，记录在数组max_i。
⑤、统计大于等于i位置的员工下标之和，记录在数组max_i_sum。

步骤二、计算方式
①、小于等于a工位每个员工的总距离：x = min_i_sum[a] * a - min_i[a]。
②、大于等于b工位每个员工的总距离：y = max_i[b] - max_i_sum[b] * b。
③、若b-a>1，则a与b之间存在工位。
创建变量c=(a+b)/2，划分更近a与更近b的工位。
a~c员工的最短位移：z = min_i[c] - min_i[a] - (min_i_sum[c] - min_i_sum[a]) * a。
c~b员工的最短位移： w = b * (min_i_sum[b] - min_i_sum[c]) - (min_i[b] - min_i[c])。
（可包含a、b工位员工，因为它们到自身的距离为0，不影响结果）

步骤三、得出答案
最终答案：x + y + z + w。

#includeusing namespace std;
#define ll long long
const int maxn = 100005;
ll X[maxn] , Y[maxn];
ll min_i[maxn] , min_i_sum[maxn];
ll max_i[maxn] , max_i_sum[maxn];
int main()
{int n,q;
    cin>>n>>q;
    
    //避免a与b上无工位的情况 
    for(int i=1;i<=n;i++)
	{scanf("%d",&X[i]);
        Y[X[i]]++;	//每个工位上的员工数量 
    }
    ll sum = 0,sum2 = 0;
    //i距离起点长度 
    for(int i=1; i<=100000; i++)
	{if(Y[i])
		{sum += i * Y[i];
            sum2 += Y[i];
        }
        //小于等于i位置的员工个数 
        min_i[i] = sum;
        //小于等于i位置的员工下标之和
        min_i_sum[i] = sum2;
    }
    sum = 0,sum2 = 0;
    for(int i=100000; i>=1; i--)
	{if(Y[i]){sum += i * Y[i];
            sum2 += Y[i];
        }
        //大于等于i位置的员工个数
        max_i[i] = sum;
        //大于等于i位置的员工下标之和 
        max_i_sum[i] = sum2;
    }
    while(q--)
	{int a, b;
        ll ans = 0;
        scanf("%d %d",&a,&b);
        if(a >b)
            swap(a , b);
        
        ll x, y, z=0, w=0;
        //1~a员工的最短位移 
        x = min_i_sum[a] * a - min_i[a];
        //b~n员工的最短位移 
        y = max_i[b] - max_i_sum[b] * b;
        
        //若a与b之间有工位
        if(b - a >1)
		{int c = (b+a)/2;
            //a~c员工的最短位移 
            z = min_i[c] - min_i[a] - (min_i_sum[c]-min_i_sum[a]) * a;
            //c~b-1员工的最短位移 
            w = b * (min_i_sum[b]-min_i_sum[c]) - (min_i[b]-min_i[c]);
        }
        
        cout<