模拟。。。 Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C

题目大意:给你一个n*m的矩阵,再给你一个小球,从(0,0)以sqrt(2)/s的速度向右上角出发,遇到边框会反弹,遇到角落就直接停止,给你一些点,问小球第一次经过这些点所需要的时间。

思路:模拟一下即可。。。注意爆int

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = 5e5 + ;
map<pair<LL, LL>, int> line;
map<pair<LL, LL>, int> ID;
vector<LL> v[maxn];
bool vis[maxn];
LL X[maxn], Y[maxn];
LL ans[maxn];
int n, m, k;
int cnt; int get_id(LL k, LL b){
if (ID.count(mk(k, b))) return ID[mk(k, b)];
ID[mk(k, b)] = ++cnt;
return cnt;
} bool check(LL k, LL b){
if (line.count(mk(k, b))) return true;
line[mk(k, b)] = ; return false;
} void cal_time(int k, int b, LL x, LL y, LL colck){
if (ID.count(mk(k, b)) == ) return ;
for (int i = ; i < v[ID[mk(k, b)]].size(); i++){
int pos = v[ID[mk(k, b)]][i];
if (vis[pos]) continue;
vis[pos] = true;
LL tx = abs(X[pos] - x), ty = abs(Y[pos] - y);
ans[pos] = colck + min(tx, ty);
}
}
void solve(){
memset(ans, -, sizeof(ans));
LL colck = ;
int ty = ;
int x = , y = ;
while(true){
int nx, ny;
if (ty == ){
if(check(, y - x)) break;
cal_time(, y - x, x, y, colck);
nx = n - x, ny = m - y;
if (nx < ny) x = n, y = y + nx, ty = ;
if (nx > ny) x = x + ny, y = m, ty = ;
}
else if (ty == ){
if(check(-, y + x)) break;
cal_time(-, y + x, x, y, colck);
nx = x, ny = m - y;
if (nx < ny) x = , y = y + nx, ty = ;
if (nx > ny) x = x - ny, y = m, ty = ;
}
else if (ty == ){
if(check(, y - x)) break;
cal_time(, y - x, x, y, colck);
nx = x, ny = y;
if (nx < ny) x = , y = y - nx, ty = ;
if (nx > ny) x = x - ny, y = , ty = ;
}
else if (ty == ){
if(check(-, y + x)) break;
cal_time(-, y + x, x, y, colck);
nx = n - x, ny = y;
if (nx < ny) x = n, y = y - nx, ty = ;
if (nx > ny) x = x + ny, y = , ty = ;
}
colck += min(nx, ny);
if(nx == ny) break;
}
} int main(){
cin >> n >> m >> k;
for (int i = ; i <= k; i++){
scanf("%lld%lld", X + i, Y + i);
int t1 = get_id(-, X[i] + Y[i]);
int t2 = get_id(, Y[i] - X[i]);
v[t1].push_back(i);
v[t2].push_back(i);
}
solve();
for (int i = ; i <= k; i++){
printf("%lld\n", ans[i]);
}
return ;
}
上一篇:MSOCache office问题


下一篇:解决ListView和ScrollView同时使用时滑动的冲突问题