华为OJ线性插值

心已赠人 2022-06-18 11:51 192阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:glober,'Helvetica Neue',Helvetica,Arial,'Lantinghei SC','Hiragino Sans GB','Microsoft YaHei','Wenquanyi Micro Hei',sans-serif; font-size:14px; line-height:20px"> 
 <tbody style=""> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px">信号测量的结果包括测量编号和测量值。存在信号测量结果丢弃及测量结果重复的情况。&nbsp;&nbsp;&nbsp;&nbsp;1.测量编号不连续的情况，认为是测量结果丢弃。对应测量结果丢弃的情况，需要进行插值操作以更准确的评估信号。&nbsp;&nbsp;采用简化的一阶插值方法,由丢失的测量结果两头的测量值算出两者中间的丢失值。&nbsp;&nbsp;假设第M个测量结果的测量值为A，第N个测量结果的测量值为B。则需要进行(N-M-1)个测量结果的插值处理。进行一阶线性插值估计的第N+i个测量结果的测量值为A+(&nbsp;(B-A)/(N-M)&nbsp;)*i&nbsp;&nbsp;(注：N的编号比M大。)&nbsp;&nbsp;例如：只有测量编号为4的测量结果和测量编号为7的测量结果，测量值分别为4和10&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;则需要补充测量编号为5和6的测量结果。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;其中测量编号为5的测量值=4&nbsp;+&nbsp;((10-4)/(7-4))*1&nbsp;=&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;其中测量编号为6的测量值=4&nbsp;+&nbsp;((10-4)/(7-4))*2&nbsp;=&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2.测量编号相同，则认为测量结果重复，需要对丢弃后来出现的测量结果。&nbsp;&nbsp;&nbsp;&nbsp;请根据以上规则进行测量结果的整理。详细描述：接口说明原型：intCleanUpMeasureInfo(MEASURE_INFO_STRUCT*&nbsp;pOriMeasureInfo,intnOriMINum,intnMaxMIRst,&nbsp;MEASURE_INFO_STRUCT*&nbsp;pMeasureInfoRst);输入参数：&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MEASURE_INFO_STRUCT*&nbsp;pOriMeasureInfo:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;原始测量结果内容，以结构数组方式存放。测量编号已经按升序排列。MEASURE_INFO_STRUCT定义包含编号和测量值，见OJ.h&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;nOriMINum:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;原始测量结果个数。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;nMaxMIRst:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;整理的测量结果最大个数。输入参数：&nbsp;&nbsp;&nbsp;&nbsp;MEASURE_INFO_STRUCT*&nbsp;pMeasureInfoRst：&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;整理的测量结果返回值：&nbsp;&nbsp;&nbsp;&nbsp;Int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;整理的测量结果个数 &nbsp;</pre> </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 数组,函数,指针,位运算,结构体</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 10M</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 128</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输入说明&nbsp; 1&nbsp;输入两个整数m,&nbsp;n 2&nbsp;输入m个数据组 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输出整理后的结果 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 2 3 4 5 5 7</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 4 5 5 7</td> 
 </tr> 
 </tbody> 
</table>

#include <iostream> 
 #include <string> 
 #include <vector>
 #include <algorithm>
 #include <map>
 
 using namespace std;
 
 int main()
 {
 	int m, n;
 	cin >> m >> n;
 	
 	map<int, int> data;
 
 	while (m > 0)
 	{
 		int key, value;
 		cin >> key >> value;
 		if (data.find(key) == data.end())
 		{
 			data.insert(make_pair(key, value));
 		}
 		m--;
 	}
 
 	int preKey, preValue;
 	int curKey, curValue;
 
 	map<int, int>::iterator it = data.begin();
 	preKey = it->first;
 	preValue = it->second;
 	it++;
 
 	cout << preKey << " " << preValue << endl;
 	for (it; it != data.end(); it++)
 	{
 		curKey = it->first;
 		curValue = it->second;
 	
 		if (it->first - preKey > 1)
 		{
 			for (int i = 1; i < it->first - preKey; i++)
 			{
 				cout << preKey + i << " " << preValue + (curValue - preValue) / (curKey - preKey)*i << endl;
 			}
 		}
 		
 		cout << curKey << " " << curValue << endl;
 	
 		preKey = curKey;
 		preValue = curValue;
 	}
 	return 0;
 }