论坛 - CSPOJ

CSPOJ

2023-10-06 17:49:26

# T1 神秘金币

考察大眼观察法，由于 $t_i$ 均不相同，而我们又可以每个时刻收集一枚金币，那么我们只需要选出前 $k$ 大的金币，然后按照 $t_i$ 从小到大的顺序收集起来就好了，不会有任何金币消失。

```c++
#include <bits/stdc++.h>
using namespace std;
int main(){
    freopen("species.in", "r", stdin);
	freopen("species.out", "w", stdout);
	int n, t, k, a[100005];
	long long sum = 0;
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> t;
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	sort(a+1, a+1+n);
	for(int i = n; i >= n - k + 1; i--){
		sum += a[i];
	}
	cout << sum << endl;
}

```

# T2 学习乘法

考察乘法的性质

两个数字的和一定，大小越接近，乘积越大。

和一定是因为本题的交换数位只能交换相同的数位，所以交换之后的和是不变的。现在我们考虑如何使得两个数字 $a,b$ 尽量接近：

从高位向低位开始看，假设对应位置相同，则继续看下一位，不同，那么我们可以钦定 $a>b$，也就是说把大的数字交换到 $a$ 的当前位，小的数字给 $b$。但是我们又希望两个数字尽量接近，所以我们应该将所有更低位中的大数字交换到数字 $b$ 上面。最终计算乘积即可。

```c++
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s1, s2; // 本题需要对每一个数位进行判断和交换，用字符串显然方便一些
	cin >> s1 >> s2;
	int st = 0;
	for(int i = 0; i < s1.size(); i++){
		if(s1[i] != s2[i]){
			if(s1[i] < s2[i]){
				swap(s1[i], s2[i]); // 钦定 s1 是更大的字符串
			}
			st = i; // 确定第一个不相同数位的位置
			break;
		}
	}
	for(int i = st + 1; i < s1.size(); i++){ // 从 st+1 开始，把剩余位置中的大数字全部给 s2，使得 s1 s2 尽量接近
		if(s1[i] > s2[i]){ 
			swap(s1[i], s2[i]);
		}
	}
//	cout << s1 << " " << s2 << endl;
	long long ans1 = 0, ans2 = 0;
	for(int i = 0; i < s1.size(); i++){ // 字符串转成数字
		ans1 = ans1 * 10 + s1[i] - '0';
		ans2 = ans2 * 10 + s2[i] - '0';
	}
	cout << ans1 * ans2 << endl;
}
```

# T3 饮料难题

通过大眼观察法可以得知本题的答案是 $n / (k-1)$，由于数字很大，可以贴一个大整数除法的模板解决本题。

本题的本质是学习除法，在原场景中（10 个饮料瓶，每 3 个瓶子换一瓶饮料，最终能喝 5 瓶饮料）可以看到，10 个饮料瓶最终喝 5 瓶饮料。根据除法的定义：总价除以数量等于单价，得到每瓶饮料的单价是 $10/5=2$。得到单价之后，继续根据除法的定义：总价除以单价等于数量，也就是说假设有 $n$ 元，则可以喝 $n / 2$ 瓶饮料。

推广到每 $k$ 个瓶子换一瓶饮料，可以简单发现答案变为 $n / (k-1)$

如果还需要证明的话，我们可以根据方程的思想来解决这个问题：

$k$ 个空瓶子 = 1 瓶饮料 + 1 个空瓶子

两边同时减 1，解得

1 瓶饮料 = $k-1$ 个空瓶子

解方程用到了五到六年级的数学，比较高端，如果可以直接用除法解决当然更好。

```c++
//50分
#include<iostream>
using namespace std;

int main(){
    freopen("beverage.in","r",stdin);
    freopen("beverage.out","w",stdout);
    int n,k;
    cin>>n>>k;
    cout<<n/(k-1);
}
```

```c++
//100分
#include<bits/stdc++.h>
using namespace std;

string n, ans; // 存储输入的字符串和最终答案的字符串
long long k, an; // 存储输入的整数和用于计算的中间结果

int main()
{
        freopen("beverage.in", "r", stdin);
	freopen("beverage.out", "w", stdout);
    cin >> n >> k; // 从标准输入读取字符串n和整数k
    
    k--; // 将k减去1，因为要计算n / (k - 1)
    
    for(int i = 0; i < n.size(); i++)
    {
        an *= 10; // 将an乘以10，为下一位字符的整数值腾出位置
        an += n[i] - '0'; // 将当前字符转换为对应的整数，并加到an中
        
        if(ans != "" || an / k != 0) // 如果ans不为空或者an除以k的商不为0
            ans += char(an / k + '0'); // 将an除以k的商转换为字符，并追加到ans末尾
        
        an %= k; // 更新an为an除以k的余数，以便进行下一次除法运算
    }
    
    cout << ans; // 输出最终答案
    
    return 0;
}

```

## T4 手术
\- 题目指出，如果一个患者来了之后发医院里一个优先级低于自己的患者正在治疗，他会很痛苦。则表明在$[t_i,k]$区间内不能有优先级高于自己的患者在自己之前治疗。因此，当前最高优先级患者应该在最早可治疗时刻开始治疗，如果往后再治疗会导致别的优先级低的患者继续等待。即优先处理优先级高的患者。

\- 初始有一个$[1,k]$区间，每次为当前未治疗患者其中优先级最高的患者服务，设该患者到达时间是$t_i$，治疗时长是$b_i$。尽可能找不早于第$t_i$个单位时间且连续治疗时长高于$b_i$的位置。比方说初始可治疗区间集合是$\{[1,10]\}$，$t_i=4,b_i=2$。抠掉区间$[4,5]$后得到可治疗区间集合是$\{[1,3],[6,10]\}$。然后当前未治疗患者其中优先级最高的患者$t_i=2,b_i=3$，则抠掉$[6,8]$，然后可治疗区间集合变成了$\{[1,3],[9,10]\}$。此时暴力复杂度是$O(n^2)$。

\- 分析性质优化复杂度。$[1,14]$优先级第$1$高的区间$[8,9]$操作后变成了$\{[1,7],[10,14]\}$。优先级第$2$高的区间$[4,5]$操作后变成了$\{[1,3],[6,7],[10,14]\}$。此时有一个优先级第$3$高的区间$[4,6]$，因为$[6,7]$塞不下$[4,6]$，所以$[4,6]$塞到了$[10,12]$，变成了$\{[1,3],[13,14]\}$。$[6,7]$被去除的原因是这个区间被优先级第$3$高的访问了但是没有用，所以优先级更低的区间不可能放在$[6,7]$里面，因为这个时刻优先级第$3$高的在等待。所以每个位置至多遍历一次，不行的话就没有意义了。使用set维护当前可治疗区间，快速定位$t_i$治疗位置。此时暴力复杂度是$O(nlogn)$。

```c++
#include<bits/stdc++.h>
using namespace std;

int main() 
{
    // 读取输入
    int n, k;
    cin >> n >> k;
    vector<int> p(n + 1, 0);    
    vector<int> t(n + 1, 0);    
    vector<int> a(n + 1, 0);    
    vector<int> b(n + 1, 0);    
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    
    // 创建一个辅助数组id，用于记录患者的编号
    vector<int> id(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        id[i] = i;
    }
    
    // 按照患者严重度排序，从小到大
    sort(id.begin() + 1, id.end(), [&](int x, int y) {
        return p[x] < p[y];
    });
    
    // 使用集合s来维护当前可理发的区间
    set<pair<int, int>> s;
    s.insert({1, k});
    
    // 初始化结果变量为0
    long long res = 0;
    
    for(int i = 1; i <= n; i++)
    {
        int c = id[i]; // 当前处理的患者编号
        
        if(s.empty()) { // 如果没有可理发的区间，跳出循环
            break;
        }
        
        // 在集合s中找到患者c可以开始理发的时间段
        auto it = s.lower_bound({t[c], 0});
        auto it2 = it;
        if(it2 != s.begin()) {
            it2--; // it2指向比t[c]小的最大时间段
        }
        
        // 判断it2所指的时间段是否包含t[c]，如果是，则使用it2作为起始时间段
        if(it2->first <= t[c] && t[c] <= it2->second) {
            it = it2;
        }
        
        if(it != s.end())
        {
            t[c] = max(t[c], it->first); // 更新患者c的到达时间
            
            if(t[c] <= it->second)
            {
                if(it->first < t[c])
                {
                    // 如果患者c的到达时间晚于it的起始时间，则将it划分为两个时间段，并插入到集合s中
                    int l = it->first;
                    int r = it->second;
                    s.erase({l, r});
                    s.insert({l, t[c] - 1});
                    s.insert({t[c], r});
                    it = s.lower_bound({t[c], 0}); // 更新it的位置
                }
                
                // 找到满足条件的连续时间段，进行理发，并计算收益
                vector<pair<int, int>> v ;
                while(it != s.end())
                {
                    int l = it->first;
                    int r = it->second;
                    
                    if(r - l + 1 >= b[c])
                    {
                        // 如果时间段长度大于等于患者c的手术时长b[c]，则进行理发操作，并增加收益
                        res += a[c];
                        s.erase(it);
                        
                        if(r - l + 1 > b[c]) {
                            s.insert({l + b[c], r});
                        }
                        
                        break ;
                    }
                    else
                    {
                        v.push_back({l, r}); // 将无法满足条件的时间段保存在v中
                        it++;
                    }
                }
                
                for(auto now : v) {
                    s.erase(now); // 移除无法满足条件的时间段
                }
            }
        }
    }
    
    // 输出结果
    cout << res << '\n';

return 0 ;
}

```

加载中...

CSPOJ

2023-10-06 17:49:49

加载中...

古明地觉

2023-10-06 20:21:05

加载中...

CSPOJ

2023-10-06 20:33:10

加载中...