2 条题解

  • 2
    @ 2025-3-13 11:24:54

    显然我们可以用一个很长的线段把所有的水瓶都覆盖

    然后因为有 mm 条线段,我们考虑剪断那一条,剪断时贪心

    预处理处两个水杯之间距离,并且从大到小排序

    我们减去 m−1m-1 个最大距离即可

    • 1
      @ 2026-10-24 11:58:32

      普通贪心,一点思维难度没有,无需多言。

      不过,我赛时犯唐写错第 2121 行的特判,没了 11pts11pts。。

      #include <bits/stdc++.h>
      #pragma GCC optimize(1)
      #pragma GCC optimize(2)
      #pragma GCC optimize(3)
      using namespace std;
      int m, n, k;
      int id[2000005], l, bl;
      priority_queue<int> q;
      int main() {
      	scanf("%d%d%d", &m, &n, &k);
      	for(int i=1; i<=k; ++i) {
      		scanf("%d", &id[i]);
      	}
          sort(id + 1, id + 1 + k);
          for(int i=1; i<=k; ++i) {
              if(id[i] != l + 1) ++bl;
      		if(l != 0 && id[i] != l + 1) q.push(-(id[i]-l-1));
      		l = id[i];
          }
      	--bl;
      	if(bl <= m - 2) {
      		printf("0");
      		return 0;
      	}
      	int ans = 0;
      	while((int)q.size() > m - 1) {
      		ans += (-q.top());
      		q.pop();
      	}
      	printf("%d", ans);
      	return 0;
      }
      
      • 1

      信息

      ID
      76
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      (无)
      递交数
      102
      已通过
      19
      上传者