hdu4995 (不错的小模拟)
模拟 不错
2023-09-11 14:14:00 时间
题意:
输入n,m,k ,给你n个点,他们在一个一维坐标上,每个点有两个值,一个是坐标,另一个是价值,然后有m组操作,每次操作给一个坐标,意思就是把当前这个坐标的点距离他最近的k个点(相等,取id小的)的价值加起来的平均数作为当前的价值,最后输出所有新得到的权值的和<n,m<=100000 ,k <= min(10 ,n - 1)>.
思路:
输入n,m,k ,给你n个点,他们在一个一维坐标上,每个点有两个值,一个是坐标,另一个是价值,然后有m组操作,每次操作给一个坐标,意思就是把当前这个坐标的点距离他最近的k个点(相等,取id小的)的价值加起来的平均数作为当前的价值,最后输出所有新得到的权值的和<n,m<=100000 ,k <= min(10 ,n - 1)>.
思路:
直接模拟就行了,一开始wa了好多次,被自己坑了,题意明明没说给的点的坐标是有序的,但是我自己一直认为是有序的所以就各种wa啊wa啊wa,呵呵!我们先把所有的数据按照坐标排序一下,排序之后记得hash下id,然后每次操作直接模拟就行了,具体的看代码,这个题没设计到什么想法,最大的时间复杂度是100000 * 10,模拟无压力 ,不知道为什么写着感觉挺开心的,虽然题目不难。
#include<stdio.h> #include<algorithm> #define N 110000 using namespace std; typedef struct { double dis ,num; int id; }NODE; NODE node[N]; int hash[N]; bool camp(NODE a ,NODE b) { return a.dis < b.dis; } int main () { int t ,n ,m ,k ,i ,a; scanf("%d" ,&t); while(t--) { scanf("%d %d %d" ,&n ,&m ,&k); for(i = 1 ;i <= n ;i ++) { scanf("%lf %lf" ,&node[i].dis ,&node[i].num); node[i].id = i; } sort(node + 1 ,node + n + 1 ,camp); for(i = 1 ;i <= n ;i ++) hash[node[i].id] = i; double Ans = 0; while(m--) { scanf("%d" ,&a); double sum = 0; int l = hash[a] - 1 ,r = hash[a] + 1; for(i = 1 ;i <= k ;i ++) { if(l < 1) sum += node[r].num ,r ++; else if(r > n) sum += node[l].num ,l --; else if(node[hash[a]].dis - node[l].dis == node[r].dis - node[hash[a]].dis) { if(node[l].id < node[r].id) sum += node[l].num ,l--; else sum += node[r].num ,r ++; } else if(node[hash[a]].dis - node[l].dis < node[r].dis - node[hash[a]].dis) sum += node[l].num ,l--; else sum += node[r].num ,r ++; } node[hash[a]].num = sum / k; Ans += node[hash[a]].num; } printf("%.6lf\n" ,Ans); } return 0; }
相关文章
- Go 稀疏数组模拟棋盘矩阵
- 132. 小组队列【队列 模拟】
- HDU 6777 Covid (简单模拟)
- HDU 5881 Tea (模拟)
- CCF 201403-3命令行选项 (STL模拟)
- 基于C语言设计的计算机模拟疫情扩散【100010757】
- Mock.js数据模拟
- 《Unity开发实战》——3.10节通过循环加载一组材质实现动画纹理(例如模拟视频)
- 【转】MySQL中增加sequence管理功能(模拟创建sequence)
- Java多线程之sleep方法阻塞线程-模拟时钟
- web项目的集成测试:模拟点击
- Unity 之 2D水插件推荐和模拟水效果制作分享
- php_curl模拟登录有验证码实例
- C# 请求数据 模拟多文件上传