官方网站建设 找磐石网络一流,网站建设中企动力最佳a4,上海做兼职哪个网站,网站建设购买数据库的流程一、遇到问题#xff1a;迭代计算时间超限
按照常规思路#xff0c;可以从begin到end逐步计算#xff0c;共需要约end-begin次运算#xff0c;时间复杂度较高#xff0c;导致时间超限。
二、解决思路#xff1a;累积
1.操作数累积部分
在输入阶段#xff0c;代码通过…一、遇到问题迭代计算时间超限
按照常规思路可以从begin到end逐步计算共需要约end-begin次运算时间复杂度较高导致时间超限。
二、解决思路累积
1.操作数累积部分
在输入阶段代码通过循环读取每个操作根据操作类型1或2更新累积的缩放系数和旋转角度。 对于缩放操作flag为1将当前操作数的缩放系数k更新为前一步操作数的缩放系数乘以当前操作的数值num。同时保持旋转角度r不变。 对于旋转操作flag为2将当前操作数的旋转角度r更新为前一步操作数的旋转角度加上当前操作的数值num。同时保持缩放系数k不变。
这样通过不断累积操作数数组x中保存了每一步的累积结果。
2. 查询阶段
对于每个查询代码读取起始和结束位置以及初始点的坐标。然后根据累积的操作数计算起始和结束位置的缩放系数和旋转角度。最后对初始点进行一次相应的缩放和旋转计算得到最终结果。
double k1 x[end].k / x[begin - 1].k;
double r1 x[end].r - x[begin - 1].r;
x1 * k1, y1 * k1;
double temp_x1 x1, temp_y1 y1;
x1 temp_x1 * cos(r1) - temp_y1 * sin(r1);
y1 temp_x1 * sin(r1) temp_y1 * cos(r1);3.总结
上述思路可以优化时间复杂度的主要原因在于通过累积操作数的方式避免了直接迭代计算。下面是具体的优化原因 累积操作数减少迭代次数 传统的计算方式是逐步迭代每一步都重新计算累积的缩放系数和旋转角度,时间复杂度为O(N)。而在优化的思路中通过累积操作数每一步都是在前一步的基础上进行更新。为操作直接提供了最终状态而不是通过逐步计算得到。 常数时间的查询操作 在查询阶段通过累积操作数可以直接计算起始和结束位置的缩放系数和旋转角度而不需要进行迭代计算。这使得查询操作的时间复杂度为常数时间而不是线性时间。
#include iostream
#include cmath
#include iomanip
using namespace std;
struct Operand
{double k;double r;
};int main() {int numberOfOperations, numberOfQueries;cin numberOfOperations numberOfQueries;Operand* x new Operand[numberOfOperations 1];for (int i 0; i numberOfOperations; i){x[i] { 1,0 };}// 输入操作数累积for (int i 1; i numberOfOperations; i){int flag;double num;cin flag num;// kif (flag 1){x[i].k x[i - 1].k * num;x[i].r x[i - 1].r;}// rif (flag 2){x[i].k x[i - 1].k;x[i].r x[i - 1].r num;}}// 输入查询for (int i 0; i numberOfQueries; i){int begin, end;double x1, y1;cin begin end x1 y1;double k1 x[end].k / x[begin - 1].k;double r1 x[end].r - x[begin - 1].r;x1 * k1, y1 * k1;double temp_x1 x1, temp_y1 y1;x1 temp_x1 * cos(r1) - temp_y1 * sin(r1);y1 temp_x1 * sin(r1) temp_y1 * cos(r1);cout fixed setprecision(3) x1 y1 endl;}return 0;
}
