DE-PR-013 增量金额修正

admin SU @ 2026-10-14 12:07:50

组织者内部题解，含参考实现。比赛中不向选手展示。

业务背景与基本概念

增量修正更新已汇总的业务金额。旧订单原贡献已包含在initial_total中，当金额改变或退款取消后应先撤掉旧贡献再加入新贡献。仅追加新值会重复计算。

公式、符号与业务口径

delta_i=new_amount_i−old_amount_i；final_total=initial_total+Σdelta_i。新值0表示该条贡献归零，仍必须扣去旧值。输入每行代表一个应处理修正，不另做去重。

样例逐步计算

初始100。第1条20→30，增量+10，总额110。第2条10→0，增量−10，总额100。输出100。若错误直接加新值，会得到130。

解题步骤与实现思路

用64位累计initial_total与每个差值，时间O(n)，业务空间O(1)。

常见错误与边界

必须理解初始总额已包含旧贡献。负增量正常，不要删掉。真实场景要保证修正事件幂等，本题不提供事件ID，所以不要求自行推断重复。

原始题面与输入输出

DE-PR-013 增量金额修正题型：综合；25分

业务与规则

每行代表一订单旧贡献和新贡献，用new-old修正总金额。输出最终整数总额，不把新额直接追加。
n=0时只输出EMPTY（即使其他常规约束要求非空，空输入为本题明示例外）。
输入保证满足给定字段与类型，无需推断未给定的业务规则。

输入第一行：n initial_total。随后n行，每行：old_amount new_amount。字段以空格分隔。

输出每行代表一订单旧贡献和新贡献，用new-old修正总金额。输出最终整数总额，不把新额直接追加。 n=0只输出EMPTY。

范围 0≤n≤10000；编号与枚举为ASCII；编号长度≤30；整数绝对值≤1e9；金额合计用64位。浮点输入小数位≤6，绝对值≤1e6；实际列约束优先于本通用范围。滑动均值window≤100，近邻k≤100；建议3秒、256MB，按平台语言校准。

样例输入 2 100 20 30 10 0

样例输出 100

各语言如何对应算法

各份程序实现上文同一计算口径。读取阶段将字符串编号与数值分开处理；中间状态负责累计、集合去重或版本选择；输出阶段才做规定排序、分页及六位小数格式化。按“解题步骤”对照各文件业务段，通用读取、哈希和排序辅助函数可先跳过，再回头理解。

Python/PyPy完整参考实现

文件：reference.py，与本题同文件夹。

Python与PyPy共用本文件。字典保存按业务键的状态，集合负责去重；Python整数可自动扩展，精确小数边界题使用Decimal。

运行方法：python reference.py；或pypy3 reference.py。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

import sys, math
from collections import defaultdict, Counter, deque
lines=sys.stdin.read().splitlines()
h=lines[0].split(); n=int(h[0])
rows=[s.split() for s in lines[1:1+n]]
if n==0:
    print("EMPTY"); sys.exit(0)
total=int(h[1])+sum(int(b)-int(a) for a,b in rows);print(total)

C完整参考实现

文件：reference.c，与本题同文件夹。

I为64位整数，F为浮点数，Group保存业务状态，Map按字符串键查找；main中的业务步骤可与上文逐项对应。

运行方法：gcc -std=c17 -O2 reference.c -lm -o reference，然后运行reference。测试数据通过标准输入送入，运行说明中的重定向不写入程序。


/* Native C17 reference. Read stdin, write stdout; no Python dependency. */
#include <ctype.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long I;
typedef double F;
typedef struct {
  char *key;
  I v[8];
  F f[8];
  char *s[4];
  int flag;
} Group;
typedef struct {
  Group *a;
  int count, cap;
  int *slots;
  int size;
} Map;
char ***L;
int *lc, lines, n;
char **h, ***r;
Map groups;
I iv(const char *s) { return strtoll(s, NULL, 10); }
F fv(const char *s) { return strtod(s, NULL); }
int eq(const char *a, const char *b) { return strcmp(a, b) == 0; }
F divide(F a, F b) { return b ? a / b : 0; }
char *dupstr(const char *s) {
  char *p = malloc(strlen(s) + 1);
  strcpy(p, s);
  return p;
}
uint64_t hash(const char *s) {
  uint64_t v = 1469598103934665603ULL;
  for (; *s; s++)
    v = (v ^ (unsigned char)*s) * 1099511628211ULL;
  return v;
}
void mapinit(Map *m) {
  m->size = 131071;
  m->slots = malloc(m->size * sizeof(int));
  for (int i = 0; i < m->size; i++)
    m->slots[i] = -1;
  m->count = 0;
  m->cap = 16;
  m->a = calloc(m->cap, sizeof(Group));
}
int lookup(Map *m, const char *k) {
  int p = hash(k) % m->size;
  while (m->slots[p] >= 0) {
    int i = m->slots[p];
    if (eq(m->a[i].key, k))
      return i;
    p = (p + 1) % m->size;
  }
  return -1;
}
int ensure(Map *m, const char *k) {
  int i = lookup(m, k);
  if (i >= 0)
    return i;
  if (m->count == m->cap) {
    m->cap *= 2;
    m->a = realloc(m->a, m->cap * sizeof(Group));
  }
  i = m->count++;
  memset(&m->a[i], 0, sizeof(Group));
  m->a[i].key = dupstr(k);
  int p = hash(k) % m->size;
  while (m->slots[p] >= 0)
    p = (p + 1) % m->size;
  m->slots[p] = i;
  return i;
}
Group *get(Map *m, const char *k) {
  int i = ensure(m, k);
  return &m->a[i];
}
char *pairkey(const char *a, const char *b) {
  size_t z = strlen(a) + strlen(b) + 2;
  char *p = malloc(z);
  snprintf(p, z, "%s\037%s", a, b);
  return p;
}
char *numpair(I a, const char *b) {
  char q[40];
  snprintf(q, sizeof(q), "%lld", a);
  return pairkey(q, b);
}
int cmpkey(const void *a, const void *b) {
  return strcmp((*(Group *const *)a)->key, (*(Group *const *)b)->key);
}
Group **ordered(Map *m, int (*cmp)(const void *, const void *)) {
  Group **a = malloc((m->count + 1) * sizeof(Group *));
  for (int i = 0; i < m->count; i++)
    a[i] = &m->a[i];
  qsort(a, m->count, sizeof(Group *), cmp ? cmp : cmpkey);
  return a;
}
int fields[8], modes[8], dirs[8], sortcount;
void sorting(int count, int *a, int *b, int *c) {
  sortcount = count;
  for (int i = 0; i < count; i++) {
    fields[i] = a[i];
    modes[i] = b[i];
    dirs[i] = c[i];
  }
}
int rowcmp(const void *a, const void *b) {
  int ia = *(const int *)a, ib = *(const int *)b;
  for (int j = 0; j < sortcount; j++) {
    int f = fields[j], v;
    if (modes[j]) {
      F x = fv(r[ia][f]), y = fv(r[ib][f]);
      v = (x > y) - (x < y);
    } else
      v = strcmp(r[ia][f], r[ib][f]);
    if (v)
      return dirs[j] * v;
  }
  return (ia > ib) - (ia < ib);
}
int *orderrows(void) {
  int *a = malloc((n + 1) * sizeof(int));
  for (int i = 0; i < n; i++)
    a[i] = i;
  qsort(a, n, sizeof(int), rowcmp);
  return a;
}
int cmpnum(const void *a, const void *b) {
  I x = (*(Group *const *)a)->v[0], y = (*(Group *const *)b)->v[0];
  return (x > y) - (x < y);
}
int cmpdaykey(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
  return c ? c : strcmp(x->s[0], y->s[0]);
}
int cmpregionmonth(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
}
int cmpint(const void *a, const void *b) {
  I x = *(const I *)a, y = *(const I *)b;
  return (x > y) - (x < y);
}
int cmpdistance(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (x->f[0] > y->f[0]) - (x->f[0] < y->f[0]);
  if (c)
    return c;
  c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
}
int cmprisk(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (y->v[0] > x->v[0]) - (y->v[0] < x->v[0]);
  if (c)
    return c;
  c = (y->v[1] > x->v[1]) - (y->v[1] < x->v[1]);
  if (c)
    return c;
  c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[2] > y->v[2]) - (x->v[2] < y->v[2]);
}
int digitstr(const char *s) {
  for (; *s; s++)
    if (*s < '0' || *s > '9')
      return 0;
  return 1;
}
I fixed6(const char *s) {
  int neg = *s == '-';
  if (*s == '-' || *s == '+')
    s++;
  I a = 0, b = 0;
  while (*s && *s != '.')
    a = a * 10 + (*s++ - '0');
  if (*s == '.')
    s++;
  int i = 0;
  while (*s && i < 6) {
    b = b * 10 + (*s++ - '0');
    i++;
  }
  while (i++ < 6)
    b *= 10;
  return (neg ? -1 : 1) * (a * 1000000 + b);
}
void load(void) {
  int cap = 32;
  L = malloc(cap * sizeof(char **));
  lc = malloc(cap * sizeof(int));
  lines = 0;
  while (1) {
    int z = 128, len = 0, c;
    char *s = malloc(z);
    while ((c = getchar()) != EOF && c != '\n') {
      if (len + 1 >= z)
        s = realloc(s, z *= 2);
      s[len++] = (char)c;
    }
    if (c == EOF && !len) {
      free(s);
      break;
    }
    s[len] = 0;
    int k = 16, q = 0;
    char **t = malloc(k * sizeof(char *));
    char *p = s;
    while (*p) {
      while (*p && isspace((unsigned char)*p))
        *p++ = 0;
      if (!*p)
        break;
      if (q == k)
        t = realloc(t, (k *= 2) * sizeof(char *));
      t[q++] = p;
      while (*p && !isspace((unsigned char)*p))
        p++;
    }
    if (q) {
      if (lines == cap) {
        cap *= 2;
        L = realloc(L, cap * sizeof(char **));
        lc = realloc(lc, cap * sizeof(int));
      }
      L[lines] = t;
      lc[lines++] = q;
    } else {
      free(t);
      free(s);
    }
    if (c == EOF)
      break;
  }
  h = L[0];
  n = (int)iv(h[0]);
  r = L + 1;
  mapinit(&groups);
}

int main(void) {
  load();
  if (n == 0) {
    puts("EMPTY");
    return 0;
  }
  I sum = iv(h[1]);
  for (int i = 0; i < n; i++)
    sum += iv(r[i][1]) - iv(r[i][0]);
  printf("%lld\n", sum);
  return 0;
}

C++完整参考实现

文件：reference.cpp，与本题同文件夹。

沿用C版的显式数组及结构体便于对照，按C++17编译；内存转换和字符串常量已适配C++类型要求，排序参数使用initializer_list。

运行方法：g++ -std=c++17 -O2 reference.cpp -o reference，然后运行reference。测试数据通过标准输入送入，运行说明中的重定向不写入程序。


/* Native C++17 reference. C-style data structures retained for comparison. */
#include <ctype.h>
#include <initializer_list>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long I;
typedef double F;
typedef struct {
  char *key;
  I v[8];
  F f[8];
  char *s[4];
  int flag;
} Group;
typedef struct {
  Group *a;
  int count, cap;
  int *slots;
  int size;
} Map;
char ***L;
int *lc, lines, n;
char **h, ***r;
Map groups;
I iv(const char *s) { return strtoll(s, NULL, 10); }
F fv(const char *s) { return strtod(s, NULL); }
int eq(const char *a, const char *b) { return strcmp(a, b) == 0; }
F divide(F a, F b) { return b ? a / b : 0; }
char *dupstr(const char *s) {
  char *p = (char *)malloc(strlen(s) + 1);
  strcpy(p, s);
  return p;
}
uint64_t hash(const char *s) {
  uint64_t v = 1469598103934665603ULL;
  for (; *s; s++)
    v = (v ^ (unsigned char)*s) * 1099511628211ULL;
  return v;
}
void mapinit(Map *m) {
  m->size = 131071;
  m->slots = (int *)malloc(m->size * sizeof(int));
  for (int i = 0; i < m->size; i++)
    m->slots[i] = -1;
  m->count = 0;
  m->cap = 16;
  m->a = (Group *)calloc(m->cap, sizeof(Group));
}
int lookup(Map *m, const char *k) {
  int p = hash(k) % m->size;
  while (m->slots[p] >= 0) {
    int i = m->slots[p];
    if (eq(m->a[i].key, k))
      return i;
    p = (p + 1) % m->size;
  }
  return -1;
}
int ensure(Map *m, const char *k) {
  int i = lookup(m, k);
  if (i >= 0)
    return i;
  if (m->count == m->cap) {
    m->cap *= 2;
    m->a = (Group *)realloc(m->a, m->cap * sizeof(Group));
  }
  i = m->count++;
  memset(&m->a[i], 0, sizeof(Group));
  m->a[i].key = dupstr(k);
  int p = hash(k) % m->size;
  while (m->slots[p] >= 0)
    p = (p + 1) % m->size;
  m->slots[p] = i;
  return i;
}
Group *get(Map *m, const char *k) {
  int i = ensure(m, k);
  return &m->a[i];
}
char *pairkey(const char *a, const char *b) {
  size_t z = strlen(a) + strlen(b) + 2;
  char *p = (char *)malloc(z);
  snprintf(p, z, "%s\037%s", a, b);
  return p;
}
char *numpair(I a, const char *b) {
  char q[40];
  snprintf(q, sizeof(q), "%lld", a);
  return pairkey(q, b);
}
int cmpkey(const void *a, const void *b) {
  return strcmp((*(Group *const *)a)->key, (*(Group *const *)b)->key);
}
Group **ordered(Map *m, int (*cmp)(const void *, const void *)) {
  Group **a = (Group **)malloc((m->count + 1) * sizeof(Group *));
  for (int i = 0; i < m->count; i++)
    a[i] = &m->a[i];
  qsort(a, m->count, sizeof(Group *), cmp ? cmp : cmpkey);
  return a;
}
int fields[8], modes[8], dirs[8], sortcount;
void sorting(int count, std::initializer_list<int> a, std::initializer_list<int> b,
             std::initializer_list<int> c) {
  sortcount = count;
  auto x = a.begin(), y = b.begin(), z = c.begin();
  for (int i = 0; i < count; i++) {
    fields[i] = *x++;
    modes[i] = *y++;
    dirs[i] = *z++;
  }
}
int rowcmp(const void *a, const void *b) {
  int ia = *(const int *)a, ib = *(const int *)b;
  for (int j = 0; j < sortcount; j++) {
    int f = fields[j], v;
    if (modes[j]) {
      F x = fv(r[ia][f]), y = fv(r[ib][f]);
      v = (x > y) - (x < y);
    } else
      v = strcmp(r[ia][f], r[ib][f]);
    if (v)
      return dirs[j] * v;
  }
  return (ia > ib) - (ia < ib);
}
int *orderrows(void) {
  int *a = (int *)malloc((n + 1) * sizeof(int));
  for (int i = 0; i < n; i++)
    a[i] = i;
  qsort(a, n, sizeof(int), rowcmp);
  return a;
}
int cmpnum(const void *a, const void *b) {
  I x = (*(Group *const *)a)->v[0], y = (*(Group *const *)b)->v[0];
  return (x > y) - (x < y);
}
int cmpdaykey(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
  return c ? c : strcmp(x->s[0], y->s[0]);
}
int cmpregionmonth(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
}
int cmpint(const void *a, const void *b) {
  I x = *(const I *)a, y = *(const I *)b;
  return (x > y) - (x < y);
}
int cmpdistance(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (x->f[0] > y->f[0]) - (x->f[0] < y->f[0]);
  if (c)
    return c;
  c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
}
int cmprisk(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (y->v[0] > x->v[0]) - (y->v[0] < x->v[0]);
  if (c)
    return c;
  c = (y->v[1] > x->v[1]) - (y->v[1] < x->v[1]);
  if (c)
    return c;
  c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[2] > y->v[2]) - (x->v[2] < y->v[2]);
}
int digitstr(const char *s) {
  for (; *s; s++)
    if (*s < '0' || *s > '9')
      return 0;
  return 1;
}
I fixed6(const char *s) {
  int neg = *s == '-';
  if (*s == '-' || *s == '+')
    s++;
  I a = 0, b = 0;
  while (*s && *s != '.')
    a = a * 10 + (*s++ - '0');
  if (*s == '.')
    s++;
  int i = 0;
  while (*s && i < 6) {
    b = b * 10 + (*s++ - '0');
    i++;
  }
  while (i++ < 6)
    b *= 10;
  return (neg ? -1 : 1) * (a * 1000000 + b);
}
void load(void) {
  int cap = 32;
  L = (char ***)malloc(cap * sizeof(char **));
  lc = (int *)malloc(cap * sizeof(int));
  lines = 0;
  while (1) {
    int z = 128, len = 0, c;
    char *s = (char *)malloc(z);
    while ((c = getchar()) != EOF && c != '\n') {
      if (len + 1 >= z)
        s = (char *)realloc(s, z *= 2);
      s[len++] = (char)c;
    }
    if (c == EOF && !len) {
      free(s);
      break;
    }
    s[len] = 0;
    int k = 16, q = 0;
    char **t = (char **)malloc(k * sizeof(char *));
    char *p = s;
    while (*p) {
      while (*p && isspace((unsigned char)*p))
        *p++ = 0;
      if (!*p)
        break;
      if (q == k)
        t = (char **)realloc(t, (k *= 2) * sizeof(char *));
      t[q++] = p;
      while (*p && !isspace((unsigned char)*p))
        p++;
    }
    if (q) {
      if (lines == cap) {
        cap *= 2;
        L = (char ***)realloc(L, cap * sizeof(char **));
        lc = (int *)realloc(lc, cap * sizeof(int));
      }
      L[lines] = t;
      lc[lines++] = q;
    } else {
      free(t);
      free(s);
    }
    if (c == EOF)
      break;
  }
  h = L[0];
  n = (int)iv(h[0]);
  r = L + 1;
  mapinit(&groups);
}

int main(void) {
  load();
  if (n == 0) {
    puts("EMPTY");
    return 0;
  }
  I sum = iv(h[1]);
  for (int i = 0; i < n; i++)
    sum += iv(r[i][1]) - iv(r[i][0]);
  printf("%lld\n", sum);
  return 0;
}

Java完整参考实现

文件：Main.java，与本题同文件夹。

Main为入口，solve为本题业务计算；long保存整数和金额，double计算普通比率，TreeMap按字符串键有序输出。精确乘积用BigInteger，不能改用int累计金额。

运行方法：javac -encoding UTF-8 Main.java，然后java Main。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
  static List<String[]> L = new ArrayList<>(), r;
  static String[] h;
  static int n;
  static StringBuilder output = new StringBuilder();
  static class G {
    long[] v = new long[8];
    double[] f = new double[8];
    String[] s = new String[4];
  }
  static TreeMap<String, G> groups = new TreeMap<>();
  static G g(Map<String, G> m, String key) {
    return m.computeIfAbsent(key, k -> new G());
  }
  static long I(String s) {
    return Long.parseLong(s);
  }
  static double N(String s) {
    return Double.parseDouble(s);
  }
  static String f(double x) {
    return String.format(Locale.ROOT, "%.6f", x);
  }
  static double div(double a, double b) {
    return b == 0 ? 0 : a / b;
  }
  static void out(Object... values) {
    for (int j = 0; j < values.length; j++) {
      if (j > 0)
        output.append(' ');
      output.append(values[j]);
    }
    output.append('\n');
  }
  static List<String[]> rows(int start, int count) {
    return new ArrayList<>(L.subList(start, start + count));
  }
  static String key(String a, String b) {
    return a + "\u001f" + b;
  }
  static BigInteger fixed(String s) {
    return new BigDecimal(s).movePointRight(6).toBigIntegerExact();
  }
  static void sortRows(List<String[]> rows, int[] fields, boolean[] numeric, int[] dirs) {
    rows.sort((a, b) -> {
      for (int j = 0; j < fields.length; j++) {
        int p = fields[j];
        int c = numeric[j] ? Double.compare(N(a[p]), N(b[p])) : a[p].compareTo(b[p]);
        if (c != 0)
          return c * dirs[j];
      }
      return 0;
    });
  }
  static void solve() throws Exception {
    if (n == 0) {
      out("EMPTY");
      return;
    }
    long sum = I(h[1]);
    for (String[] x : r) sum += I(x[1]) - I(x[0]);
    out(sum);
  }
  public static void main(String[] args) throws Exception {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String line;
    while ((line = reader.readLine()) != null)
      if (!line.trim().isEmpty())
        L.add(line.trim().split("\\s+"));
    h = L.get(0);
    n = h[0].matches("[0-9]+") ? Integer.parseInt(h[0]) : 0;
    r = rows(1, Math.min(n, L.size() - 1));
    solve();
    System.out.print(output);
  }
}

Kotlin完整参考实现

文件：Main.kt，与本题同文件夹。

main读取输入，solve执行本题步骤。val表示不可重新赋值，var表示可变状态；LongArray保存整数，DoubleArray保存比率，TreeMap固定输出顺序。!!仅用于题面保证已存在的数据。

运行方法：kotlinc Main.kt -jvm-target 17 -include-runtime -d main.jar，然后java -jar main.jar。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

import java.math.BigDecimal
import java.math.BigInteger
import java.util.Locale
import java.util.TreeMap

data class G(
  val v: LongArray = LongArray(8),
  val f: DoubleArray = DoubleArray(8),
  val s: Array<String?> = arrayOfNulls(4),
)

lateinit var L: List<Array<String>>
lateinit var h: Array<String>
lateinit var r: MutableList<Array<String>>
var n = 0
val output = StringBuilder()
val groups = TreeMap<String, G>()

fun g(m: MutableMap<String, G>, key: String): G = m.getOrPut(key) { G() }

fun I(s: String): Long = s.toLong()

fun N(s: String): Double = s.toDouble()

fun f(x: Number): String = String.format(Locale.ROOT, "%.6f", x.toDouble())

fun div(a: Number, b: Number): Double =
  if (b.toDouble() == 0.0) 0.0 else a.toDouble() / b.toDouble()

fun out(vararg values: Any?) {
  output.append(values.joinToString(" ")).append('\n')
}

fun rows(start: Int, count: Int): MutableList<Array<String>> =
  L.subList(start, start + count).toMutableList()

fun key(a: String, b: String): String = a + "\u001f" + b

fun fixed(s: String): BigInteger = BigDecimal(s).movePointRight(6).toBigIntegerExact()

fun sortRows(
  rows: MutableList<Array<String>>,
  fields: IntArray,
  numeric: BooleanArray,
  dirs: IntArray,
) {
  rows.sortWith(
    Comparator { a, b ->
      var result = 0
      for (j in fields.indices) {
        val p = fields[j]
        val c = if (numeric[j]) N(a[p]).compareTo(N(b[p])) else a[p].compareTo(b[p])
        if (c != 0) {
          result = c * dirs[j]
          break
        }
      }
      result
    }
  )
}

fun solve() {
  if (n == 0) {
    out("EMPTY")
    return
  }
  var sum = I(h[1])
  for (x in r) sum += I(x[1]) - I(x[0])
  out(sum)
}

fun main() {
  L =
    System.`in`
      .bufferedReader()
      .lineSequence()
      .filter { it.isNotBlank() }
      .map { it.trim().split(Regex("\\s+")).toTypedArray() }
      .toList()
  h = L[0]
  n = h[0].toIntOrNull() ?: 0
  r = rows(1, minOf(n, L.size - 1))
  solve()
  print(output)
}

JavaScript/Node.js完整参考实现

文件：reference.js，与本题同文件夹。

在Node.js运行，Map和Set保存状态；Number计算普通数值，超过安全整数范围的金额累计及精确乘积使用BigInt。

运行方法：node reference.js。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

// Node.js reference. All task code runs natively in JavaScript.
const fs = require('fs');
const lines = fs.readFileSync(0, 'utf8').trim().split(/\r?\n/).filter(x => x.trim()).map(x => x
  .trim().split(/\s+/));
const h = lines[0];
let n = Number(h[0]),
  r = lines.slice(1, 1 + n);
const N = Number,
  cmp = (a, b) => a < b ? -1 : a > b ? 1 : 0;
const f = x => Number(x).toFixed(6),
  div = (a, b) => b ? a / b : 0;
const out = [];
const emit = (...a) => out.push(a.join(' '));
const grouped = new Map();
const get = (k, init = () => [0, 0]) => {
  if (!grouped.has(k)) grouped.set(k, init());
  return grouped.get(k);
};
const keys = m => [...m.keys()].sort(cmp);
const pair = (a, b) => JSON.stringify([a, b]);

function fixed6(s) {
  let neg = s[0] === '-';
  s = s.replace(/^[+-]/, '');
  let [a, b = ''] = s.split('.');
  return (neg ? -1n : 1n) * (BigInt(a) * 1000000n + BigInt((b + '000000').slice(0, 6)));
}

if (n === 0) {
  console.log("EMPTY");
  process.exit(0);
}
let sum = N(h[1]);
for (const [a, b] of r) sum += N(b) - N(a);
emit(sum);
process.stdout.write(out.join("\n") + (out.length ? "\n" : ""));

Bash（GNU awk）完整参考实现

文件：reference.sh，与本题同文件夹。

Bash负责启动和环境检查，GNU awk在同一脚本中解析数据并完成本题算法。C[行,列]从1计数，num按十进制转换，i输出整数，f输出六位小数；-M启用GMP/MPFR，PREC=256。不是普通awk兼容脚本，必须满足运行依赖。

运行方法：bash reference.sh（需支持-M的GNU awk）。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

#!/usr/bin/env bash
# Requires GNU awk with GMP/MPFR (-M). No Python, Java or Node.js subprocess.
set -euo pipefail
export LC_ALL=C
if ! command -v gawk >/dev/null 2>&1; then
  printf "%s\n" "GNU awk (gawk) with -M support is required" >&2
  exit 1
fi
exec gawk -M -v PREC=256 '
BEGIN { OFS=" "; OFMT="%.0f"; CONVFMT="%.30g" }
NF>0 { lines++; nf[lines]=NF; for(j=1;j<=NF;j++) C[lines,j]=$j }
function num(s) { return s+0 }
function eq(a,b) { return (a "")== (b "") }
function cmpstr(a,b) { a=a "";b=b "";return a<b?-1:a>b?1:0 }
function f(x) { return sprintf("%.6f",x) }
function i(x) { return sprintf("%.0f",x) }
function div(a,b) { a+=0;b+=0;return b!=0?a/b:0 }
function abs(x) { return x<0?-x:x }
function min(a,b) { return a<b?a:b }
function max(a,b) { return a>b?a:b }
function floor(x, t) { t=int(x);return t>x?t-1:t }
function fixed(s, a,negative,b) {
  negative=substr(s,1,1)=="-";sub(/^[+-]/,"",s);split(s,a,/[.]/)
  b=substr(a[2] "000000",1,6)
  return (negative?-1:1)*(num(a[1])*1000000+num(b))
}
function pair(a,b) { return (a "") SUBSEP (b "") }
function group(k) { groups[k]=1 }
function sorted_groups() { return asorti(groups,idx,"@ind_str_asc") }
function compare_rows(a,av,b,bv, j,p,x,y,c) {
  for(j=1;j<=sort_count;j++) {
    p=fields[j];x=C[base+a-1,p];y=C[base+b-1,p]
    if(modes[j]){x=num(x);y=num(y);c=x<y?-1:x>y?1:0}else c=cmpstr(x,y)
    if(c)return dirs[j]*c
  }
  return (a+0)<(b+0)?-1:(a+0)>(b+0)?1:0
}
function order_rows(fs,ms,ds, j) {
  sort_count=split(fs,fields," ");split(ms,modes," ");split(ds,dirs," ")
  delete order;for(j=1;j<=n;j++)order[j]=j
  return asorti(order,idx,"compare_rows")
}
function compare_neighbors(a,av,b,bv, c) {
  c=dist[a]<dist[b]?-1:dist[a]>dist[b]?1:0;if(c)return c
  c=cmpstr(C[base+a-1,1],C[base+b-1,1]);return c?c:(a+0)-(b+0)
}
function compare_day_key(a,av,b,bv, c) {
  c=values[a,1]<values[b,1]?-1:values[a,1]>values[b,1]?1:0
  return c?c:cmpstr(strings[a,1],strings[b,1])
}
function compare_region_month(a,av,b,bv, c) {
  c=cmpstr(strings[a,1],strings[b,1]);return c?c:values[a,1]-values[b,1]
}
function compare_risk(a,av,b,bv, c) {
  c=values[b,1]-values[a,1];if(c)return c
  c=values[b,2]-values[a,2];if(c)return c
  c=cmpstr(strings[a,1],strings[b,1]);return c?c:(a+0)-(b+0)
}
END {
  for(j=1;j<=nf[1];j++)h[j]=C[1,j]
  n=num(h[1]);base=2
  if(n==0){print "EMPTY";exit}
  sum=num(h[2]);for(row=base;row<base+n;row++)sum+=num(C[row,2])-num(C[row,1]);print i(sum)

}
'

测试与评分解释

公开样例用于理解与自测；隐藏测试分项计分，每题25分。现有4组主要覆盖空输入、单记录、重复及次序变化；它们不代表所有专业边界已充分覆盖。命题人还应独立设计能区分错误实现的测试，例如错误分母、错误等号、先过滤后去重、全部排序键反转及精度阈值。参考实现通过已有测试并不能证明题库已经达到正式比赛部署标准。

ID

654

Time

2000ms

Memory

256MiB

Difficulty

Tags

# Submissions

Accepted

Uploaded By

admin

1 solutions