探测器 P1226

思路

1.准备

不多讲

#include <bits/stdc++.h> #define ll long long using namespace std; int n,m; ll ans;

2.输入

std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;

3.分析

由于题目要的是最少，就让房子间隔尽可能的远，咱们枚举右端点，对于探测器i-1和i来说，如果Ci<Ci-1，最少会有Ci-1 - Ci 个电话。用结构体存储，再排序计算。

4.结构体定义

5.输出

最后代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
struct T 
{
    int p;
    LL c;
} t[MAXN];
int n, m;
LL cnt, ans;
bool cmp(T x, T y)
{
    return x.p < y.p;
}
int main()
{
    cin >> n >> m;   
    for (int i = 1; i <= n; i++)
        cin >> t[i].p >> t[i].c;
    sort(t + 1, t + n + 1, cmp);  
    for (int i = 1; i <= n + 1; i++)
    {
        if (t[i].c < t[i - 1].c)
            ans += t[i - 1].c - t[i].c;
    }   
    cout << ans << endl;  
    return 0;
}

点赞点赞，不点赞，去你家偷马桶盖！！！

P1226 【挑战题】探测器

题目是要计算在一个月内可能发生的最小电话通话次数。这些通话被安装在房间间的探测器探测到，而这些探测器能探测到在它们东边和西边的房子之间的通话。

本蒟蒻写不出什么解释

要对探测器的位置和通话次数的数组进行排序，然后比较每个探测器与前一个探测器之间的通话次数差，如果当前的探测器的通话次数多于前一个探测器的通话次数，那么它就会增加总的通话次数。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
struct T 
{
    int p;
    LL c;
} t[MAXN];
int n, m;
LL cnt, ans;
bool cmp(T x, T y)
{
    return x.p < y.p;
}
int main()
{
    cin >> n >> m;   
    for (int i = 1; i <= n; i++)
        cin >> t[i].p >> t[i].c;
    sort(t + 1, t + n + 1, cmp);  
    for (int i = 1; i <= n + 1; i++)
    {
        if (t[i].c < t[i - 1].c)
            ans += t[i - 1].c - t[i].c;
    }   
    cout << ans << endl;  
    return 0;
}

因为题目要求通话数量尽量少，也就是需要让每个通话的两个房子尽量远。可以从左往右看每一个探测器，只统计每个通话的右端点。对于两个探测器$i-1$和$i$，如果$C_{i} < C_{i-1}$，那么此处至少产生$C_{i-1} - C_{i}$个右端点，对每个探测器求和即可。注意需要统计最后一个探测器，因此可以假设还有第$n+1$个探测器，且$C_{n+1}=0$。

typedef long long LL;
const int MAXN = 100005;
struct T {
    int p;
    LL c;
} t[MAXN];
int n, m;
LL cnt, ans;
bool cmp(T x, T y)
{
    return x.p < y.p;
}

sort(t + 1, t + n + 1, cmp);
for (int i = 1; i <= n + 1; i++)
    if (t[i].c < t[i - 1].c)
        ans += t[i - 1].c - t[i].c;