WA爆0求调

常规
1 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
struct node{
  int l,r,v,p,id;
  bool operator<(node a) const{
    if(a.p==this->p)return a.v<this->v;
    return a.p<this->p;
  }
};
int main(){
  int t;
  cin>>t;
  for(int z=0;z<t;z++){
    int n,W,L,v,p,ans,l,r;
    bool a[100001],e=1,b[15010];
    vector<node>c;
    node u;
    memset(a,0,sizeof(a));
    cin>>n>>L>>W;
    ans=n;
    for(int i=0;i<n;i++){
      cin>>u.v>>u.p;
      u.l=u.v-floor(sqrt(u.p*u.p-W*W/4.0));
      u.r=u.v+ceil(sqrt(u.p*u.p-W*W/4.0));
      if(u.l<1)u.l=1;
      if(u.r>L)u.r=L;
      u.id=i;
      c.push_back(u);
    }for(auto i:c){
      for(int j=i.l;j<i.r;j++){
        if(a[j]==0)b[i.id]=1;
        a[j]=1;
      }if(!b[i.id])ans--;
    }for(int i=1;i<=L;i++){
      if(!a[i]){
        cout<<"-1\n";
        e=0;
        break;
      }
    }if(e)cout<<ans<<"\n";
  }return 0;
}
2 个赞
2

题目描述：

长L米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？

image.png

输入格式：

输入包含若干组测试数据。

第一行一个整数 T 表示数据组数；

每组数据的第一行是整数n 、L 和 W；

接下来的 n 行，每行包含两个整数，给出一个喷头的位置和浇灌半径（上面的示意图是样例输入第一组数据所描述的情况）。

输出格式：

输出一个数字，表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪，则输出“-1”。

样例输入：

3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1

样例输出：

6
2
-1

约定：

n<=15000

1 个赞
3

解题思路

1. 计算每个喷头的作用范围：

  • 对每个喷头 iii，其作用范围是 [pi−ri,pi+ri][p_i - r_i, p_i + r_i][pi​−ri​,pi​+ri​]，即左端点 pi−rip_i - r_ipi​−ri​ 和右端点 pi+rip_i + r_ipi​+ri​。

2. 区间合并问题：

  • 我们需要将这些区间按照左端点从小到大排序。
  • 然后，采用贪心算法来选择最少的喷头。具体策略是：从当前的浇灌位置开始，选择一个喷头，它能够扩展当前覆盖区间的右端点，直到覆盖整个草坪的长度。

3. 贪心算法步骤：

  • 将所有喷头的区间按左端点排序。
  • 初始化当前的覆盖范围 current_end 为 0。
  • 遍历所有喷头，选择能够扩展当前覆盖范围的最远右端点的喷头，直到 current_end 大于或等于 LLL。

4. 判断无法覆盖的情况：

  • 如果在某个位置找不到能够扩展当前覆盖范围的喷头，则输出 -1。
1 个赞
4
  1. 输入与输出：
  • 先读入测试用例数 TTT，然后对每个测试用例进行处理。
  • 每个测试用例中，首先读取草坪的长度 LLL 和宽度 WWW，然后读取每个喷头的位置和半径。
  1. 数据结构：
  • Sprinkler 结构体保存喷头的位置和半径，并提供一个 getCoverage() 方法返回该喷头的覆盖区间。
  1. 核心算法：
  • 对所有喷头的覆盖范围进行排序，排序的依据是左端点。
  • 然后使用贪心算法依次选择能够扩展当前覆盖区间的喷头，直到覆盖整个草坪的长度 LLL。
  1. 处理失败情况：
  • 如果遍历过程中发现没有喷头可以扩展覆盖区间，则返回 -1，表示无法覆盖整个草坪。

复杂度分析

  • 时间复杂度：排序操作是 O(nlog⁡n)O(n \log n)O(nlogn)，然后线性扫描喷头是 O(n)O(n)O(n)。因此，总时间复杂度是 O(nlog⁡n)O(n \log n)O(nlogn)，适合 n≤15000n \leq 15000n≤15000 的情况。
  • 空间复杂度：需要存储喷头的覆盖区间，空间复杂度为 O(n)O(n)O(n)。
1 个赞
5 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Sprinkler {
    int position;
    int radius;
    
    // 计算该喷头的覆盖区间
    //
};

bool compare(Sprinkler a, Sprinkler b) {
    return a.position - a.radius < b.position - b.radius;
}

int solve(int n, int L, int W, vector<Sprinkler>& sprinklers) {
    // 1. 将喷头按左端点排序
    //
    sort(ranges.begin(), ranges.end());

    int current_end = 0; // 当前覆盖到的最远位置
    int count = 0; // 需要的喷头数
    
    for (int i = 0; i < n; ++i) {
        // 如果当前的喷头无法覆盖到当前需要覆盖的位置，跳过
        //

        // 找到能够扩展覆盖的最远的喷头
        //
        i--;  // 回退一步，确保每次只选一个喷头
        
        if (max_reach >= L) return count + 1; // 如果覆盖到草坪末尾，返回喷头数
        
        current_end = max_reach; // 更新当前覆盖的位置
        count++;
    }
    
    // 如果遍历完后仍未覆盖草坪，返回-1
    return current_end >= L ? count : -1;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, L, W;
        cin >> n >> L >> W;
        
      //
      //
      //
        int result = solve(n, L, W, sprinklers);
        cout << result << endl;
    }
    return 0;
}
2 个赞