6.4 cf E(题目难理解)

Problem - E - Codeforces

翻译：

小车在0点，时间为0时开始移动，从0，a1,a2......ak有k+1个标志点，对应的时间为0，b1,b2...bk

在任意两个标志间，小车以匀速行驶，所以

v=ai+1​−ai​​ / bi+1​−bi​

现在有q个访问，每个访问点都是整数

输入描述：

第一行 n,k,q

第二行（不懂）

 contains k𝑘 integers ai𝑎𝑖 (1≤ai≤n1≤𝑎𝑖≤𝑛; ai<ai+1𝑎𝑖<𝑎𝑖+1 for every 1≤i≤k−11≤𝑖≤𝑘−1; ak=n𝑎𝑘=𝑛).

意思是0,k1...对应的ai

第三行  同理

接下来询问

难点

查找到当前位置

解决措施：upper__boud(begin,end,find)

在有序的情况下，用upper__bound指向上一个

代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int N=1e5+10;
typedef long long ll;
int a[N],b[N];
int main()
{IOSint t;cin>>t;while(t--){int n,k,q;cin>>n>>k>>q;a[0]=0;b[0]=0;for(int i=1;i<=k;i++) cin>>a[i];for(int i=1;i<=k;i++) cin>>b[i];while(q--){int d;cin>>d;if(d==n) {cout<<b[k];cout<<" ";continue;}int ans=upper_bound(a,a+k+1,d)-(a+1);cout<<b[ans]+1ll*(b[ans+1]-b[ans])*(d-a[ans])/(a[ans+1]-a[ans])<<" ";}cout<<endl;}return 0;
}