Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:不知道是我题读错了还是测试数据有问题

Posted by 1966412011 at 2019-10-06 23:14:55 on Problem 3171
In Reply To:不知道是我题读错了还是测试数据有问题 Posted by:1966412011 at 2019-10-06 23:13:57
> 按照提上的意思,如果有第0秒,第0秒也应该有有牛,我有一份代码,测试数据
> 3 0 4
> 0 0 1
> 1 2 3
> 3 4 1
> 我的代码输出4,这个代码依然可以通过
#include <cstdio>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
//#include <unordered_map>

#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define l(x) x<<1
#define r(x) x<<1|1
#define ms(a,b) memset(a,b,sizeof(a))

using namespace std;

struct node {
	int s;
	int t;
	int val;
};

bool cmp(const node& a, const node& b) {
	return a.t < b.t;
}

int n, m, e;
int dp[90000];
node demo[11000];

const int MAX_N = 1 << 17;
int len, dat[2 * MAX_N - 1];

void init(int n_) {
	len = 1;
	while (len < n_)
		len *= 2;

	for (int i = 0; i < len * 2 - 1; i++)
		dat[i] = INF;
}

void update(int k, int a) {
	k += len - 1;
	dat[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
	}
}

int query(int a,int b,int k,int l,int r){
	if (r <= a || b <= l)
		return INF;

	if (a <= l && r <= b) return dat[k];
	else {
		int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
}

int query(int a, int b) {
	return query(a, b, 0, 0, len);
}

int get(int k) {
	return dat[k + len - 1];
}


int main(void) {
	scanf("%d%d%d", &n, &m, &e);

	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &demo[i].s, &demo[i].t,&demo[i].val);
	}
	init(e);
	update(m, 0);
	sort(demo, demo + n,cmp);


	ms(dp, INF);
	dp[0] = 0;

	for (int i = 0; i < n; i++) {
		int v = min(dp[demo[i].t], query(demo[i].s - 1, demo[i].t+1)+ demo[i].val);
		dp[demo[i].t] = v;
		update(demo[i].t, v);
	}

	if(dp[e]!=INF)
		printf("%d\n", dp[e]);
	else
		printf("-1\n");

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator