| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛

已结贴   问题点数：80  回复次数：4

public class Main {
const int MAXN = 1e5 + 10;
LL INF = 2e9 + 10, B = 20;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, jp[MAXN][21], nxa[MAXN], nxb[MAXN], flag[MAXN], h[MAXN];
LL f[MAXN][21], da[MAXN][21], db[MAXN][21];
struct Node {
LL Hi, id;
bool operator < (const Node &rhs) const{
return Hi == rhs.Hi ? h[id] < h[rhs.id] : Hi < rhs.Hi;
}
};
int get(int x, int y) {
return abs(h[x] - h[y]);
}
set<Node> s;
void Pre() {
s.insert((Node) {-INF * 2, 0}); s.insert((Node) {INF * 2, 0});
s.insert((Node) {-INF * 2 + 1, 0}); s.insert((Node) {INF * 2 + 1, 0});
s.insert((Node) {h[N], N});
memset(f, 0x3f, sizeof(f));
for(int i = N - 1; i >= 1; i--) {
set<Node> :: iterator y = s.lower_bound((Node) {h[i], i});
vector<Node> tmp; tmp.clear();
tmp.push_back((Node) {get(y -> id, i), y -> id}); y++;
tmp.push_back((Node) {get(y -> id, i), y -> id}); y--; y--;
tmp.push_back((Node) {get(y -> id, i), y -> id}); y--;
tmp.push_back((Node) {get(y -> id, i), y -> id});
sort(tmp.begin(), tmp.end());
nxa[i] = tmp[1].id;
nxb[i] = tmp[0].id;
s.insert((Node) {h[i], i});
if(tmp[1].id != 0 && tmp[0].id != 0) f[i][0] = tmp[1].Hi + db[tmp[1].id][0];
jp[i][0] = nxb[nxa[i]];
da[i][0] = get(i, nxa[i]);
db[i][0] = get(i, nxb[i]);
}
for(int j = 1; j <= B; j++)
for(int i = 1; i <= N; i++) {
if(jp[i][j - 1])
jp[i][j] = jp[jp[i][j - 1]][j - 1],
f[i][j] = f[i][j - 1] + f[jp[i][j - 1]][j - 1],
da[i][j] = f[i][j] == INF ? 0 : da[i][j - 1] + da[jp[i][j - 1]][j - 1];
}

}
void print() {
for(int i = 1; i <= N; i++) printf("**%d\n", f[i][0]);
}
Pair Query(int pos, int val) {
LL a1 = 0, a2 = 0;
for(int i = B; ~i; i--)
if(f[pos][i] <= val)
val -= f[pos][i], a1 += da[pos][i], a2 += f[pos][i] - da[pos][i], pos = jp[pos][i];
if(da[pos][0] <= val) a1 += da[pos][0];
return MP(a1, a2);
}
signed main() {
// freopen("drive3.in", "r", stdin);
//   freopen("a.out", "w", stdout);
for(int i = 1; i <= N; i++) h[i] = read(); h[0] = INF;

Pre();
// print();
int X0 = read(), ans = N;
double tmp = 1e22;
for(int i = 1; i <= N; i++) {
Pair now = Query(i, X0);
if(now.se == 0) continue;
if((double)now.fi / now.se < tmp) tmp = (double)now.fi / now.se, ans = i;
}
printf("%d\n", ans);
int M = read();
while(M--) {
int Si = read(), Mi = read();
Pair now = Query(Si, Mi);
printf("%d %d\n", now.fi, now.se);
}
return 0;
}
}

得分:40
？？？你这写的是啥哦？C++？

saber,别哭.
得分:40

```public class Test extends JPanel {
/**
*
*/
private static final long serialVersionUID = 1L;
static int size=40;
static class Cell {
int x;
int y;
public int getX() {
return x;
}
public int getY() {
return y;
}
public Cell(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
static Cell cell = new Cell(0, 0);
static Cell cell2 = new Cell(280, 280);
@Override
public void paint(Graphics g) {
g.setColor(Color.WHITE);
g.fillRect(0, 0, 400, 400);
g.setColor(Color.RED);
int size=40;
for(int i=1; i<8; i++)
g.drawLine(i*size, 0, i*size, 320);
for(int j=1; j<8; j++)
g.drawLine(0, j*size, 320, j*size);
g.fillOval(cell.x, cell.y, size, size);
g.fillOval(cell2.x, cell2.y, size, size);
}

private void start() {
JFrame jframe = new JFrame();
jframe.setVisible(true);
jframe.setSize(400, 400);
jframe.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
new Timer().schedule(new TimerTask() {

@Override
public void run() {
int size=Test.size-12;
if(cell.x+size>cell2.x&&cell.x<cell2.x+size&&
cell.y+size>cell2.y&&cell.y<cell.y+size) {
JOptionPane.showMessageDialog(Test.this, "Boom!");
cell.x = -1;
cell.y = -1;
}else {
if(cell.x>=0) {
cell.y+=1;
cell.x+=1;
}
}
repaint();
}
}, 10, 10);
}
public static void main(String[] args) {
new Test().start();
}
}
```

[此贴子已经被作者于2018-11-19 23:39编辑过]

得分:0

```public class Main {
private static int X;
private static int Y;
private static Car[] cars;
enum Direction {
N,W,S,E
}
static class Car {
int id;
Direction dir;
int x;
int y;
public Car(int id,int x,int y,String strDir) {
this.id = id+1;
this.x = x;
this.y = y;
dir = Direction.valueOf(strDir);
}
public void move() {
if(dir == Direction.N) {
check(x,y+1);
this.y += 1;
} else if(dir == Direction.W) {
check(x-1,y);
this.x -= 1;
} else if(dir == Direction.E) {
check(x+1,y);
this.x += 1;
} else if(dir == Direction.S) {
check(x,y-1);
this.y -= 1;
}
}
public void check(int x,int y){
if(x>X || x<0 || y>Y || y<0) {
System.out.println("小车"+this.id+"撞墙了");
System.exit(0);
}
for(Car car : cars) {
if(car.x==x && car.y==y) {
System.out.println("小车"+this.id+"撞到了小车"+car.id);
System.exit(0);
}
}
}
public void rotation(String str) {
if(str.equals("L")) {
if(dir == Direction.N) {
dir = Direction.W;
} else if(dir == Direction.W) {
dir = Direction.S;
} else if(dir == Direction.S) {
dir = Direction.E;
}  else if(dir == Direction.E) {
dir = Direction.N;
}
} else {
if(dir == Direction.N) {
dir = Direction.E;
} else if(dir == Direction.W) {
dir = Direction.N;
} else if(dir == Direction.S) {
dir = Direction.W;
}  else if(dir == Direction.E) {
dir = Direction.S;
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
X = scan.nextInt();
Y = scan.nextInt();
int n = scan.nextInt();
int m = scan.nextInt();
cars = new Car[n];
for(int i=0;i<n;i++) {
cars[i] = new Car(i,scan.nextInt(),scan.nextInt(),scan.next());
}
for(int i=0;i<m;i++) {
int id = scan.nextInt();
String command = scan.next();
int time = scan.nextInt();
for(int j=0;j<time;j++) {
if(command.equals("F")) {
cars[id-1].move();
} else {
cars[id-1].rotation(command);
}
}
}
System.out.println("Perfect");
scan.close();
}
}```

5 4
2 2
1 1 E
5 4 W
1 L 96
1 F 2
Perfect

5 4
2 2
1 1 E
5 4 W
1 F 7
2 F 7

5 4
2 4
1 1 E
5 4 W
1 F 3
2 F 1
1 L 1
1 F 3

saber,别哭.
得分:0

• 5
• 1/1页
• 1

Powered by Discuz, Processed in 0.047328 second(s), 8 queries.