在已通过代码里发现的
#include<bits/stdc++.h>
usingnamespacestd;
typedeflonglongLL;
constintN = 1e5+5;
//struct HT{
// static const int P = 31630;//sqrt(1e9)
// int head[P], nxt[N], tot;
// int id[N];
// LL val[N];
// void init(){
// for(int i=1; i <= tot; i++)
// head[id[i] % P] = 0;
// tot = 0;
// }
// void insert(int x, LL y){
// int t = x % P;
// id[++tot] = x; val[tot] = y;
// nxt[tot] = head[t]; head[t] = tot;
// }
// LL find(int x){
// for(int i=head[x % P]; i; i=nxt[i])
// if(id[i] == x)
// return val[i];
// return -1;
// }
// void update(int x, LL y){
// for(int i=head[x % P]; i; i=nxt[i])
// if(id[i] == x)
// val[i] += y;
// }
//}ha, ha2;
//struct HT2{
// static const int P = 31630;//sqrt(1e9)
// int head[P], nxt[N], tot;
// int id[N];
// int C[N];
// LL val[N];
// void init(){
// for(int i=1; i <= tot; i++)
// head[id[i] % P] = 0;
// tot = 0;
// }
// void insert(int x, int c, LL y){
// int t = x % P;
// id[++tot] = x; val[tot] = y; C[tot] = c;
// nxt[tot] = head[t]; head[t] = tot;
// }
// LL find(int x, int c){
// for(int i=head[x % P]; i; i=nxt[i])
// if(id[i] == x && C[i] == c)
// return val[i];
// return -1;
// }
// void update(int x, int c, LL y){
// for(int i=head[x % P]; i; i=nxt[i])
// if(id[i] == x && C[i] == c)
// val[i] += y;
// }
//}ha3;
structnode{
intid, h, c, p;
}tr[N];
boolcmp(node x, node y){
returnx.h < y.h;
}
LL C[205];
LL sum[N];
LL sumC[N];
constLL INF = 0x3f3f3f3f3f3f3f3fll;
intmain(){
intn,i,j,k;
while(scanf("%d",&n)!=EOF){
sum[0] = 0;
sumC[0] = 0;
// ha.init();
// ha2.init();
// ha3.init();
for(i=1; i<=n; i++)
scanf("%d%d%d",&tr[i].h, &tr[i].c, &tr[i].p);
sort(tr+1, tr+n+1, cmp);
for(i=1; i<=n; i++){
// tr[i].id = i;
// C[tr[i].c] += tr[i].p;
sum[i] = sum[i-1] + tr[i].p;
sumC[i] = sumC[i-1] + (LL)tr[i].p*tr[i].c;
// ha.insert(tr[i].h, i);
// if(ha2.find(tr[i].h) != -1)
// ha2.update(tr[i].h, tr[i].p);
// else
// ha2.insert(tr[i].h, tr[i].p);
// if(ha3.find(tr[i].h, tr[i].c) == -1)
// ha3.insert(tr[i].h, tr[i].c, tr[i].p);
// else
// ha3.update(tr[i].h, tr[i].c, tr[i].p);
}
memset(C, 0, sizeofC);
LL ans = INF;
for(i=1, j=1; i<=n; i=j){
while(j+1 <= n && tr[j+1].h == tr[i].h)
j++;
LL tmp = sumC[n] - sumC[j];
LL cut = sum[i-1] - (sum[j] - sum[i-1]) + 1;
LL cnt = 0;
for(k=1; k<=200; k++){
cnt += C[k];
tmp += C[k]*k;
if(cnt >= cut){
cnt -= C[k];
tmp -= C[k]*k;
tmp += (cut - cnt)*k;
break;
}
}
ans = min(ans, tmp);
for(k=i; k<=j; k++)
C[tr[k].c] += tr[k].p;
j++;
}
printf("%lld\n",ans);
}
}
/*
3
3 5 1
3 10 1
3 5 2
*/
全部评论
(1) 回帖