柚子快報激活碼778899分享：藍橋杯——泡澡
柚子快報激活碼778899分享：藍橋杯——泡澡
?????????題目沒有給n的范圍，讓我天真的以為數(shù)據(jù)不會太大，結(jié)果又寫了個超時的代碼，具體如下：
#include
using namespace std;
using ll = long long;
const int maxn = 1e6;
ll P[maxn];
ll d[maxn];
int main()
{
int n;
ll w;
cin >> n >> w;
for (int i = 1; i <= n; i++){
int s, t, p; cin >> s >> t >> p;
for (int i = 1; i <= t - s; i++) {
P[i] += p;
if (P[i] > w){
cout << "No";
return 0;
}
}
}
cout << "Yes";
return 0;
}
? ? ? ? ?思路很簡單，就是雙重循環(huán)，每次檢測P數(shù)組的值是否大于w。但又又又又又超時啦！
?差分
? ? ? ? 這題依然是用差分解決。其實題目中給了范圍s~t，就給人一種前綴和或者差分的感覺。結(jié)果果然是要用差分。區(qū)別于普通差分模板，這的一個關(guān)鍵在于默認差分數(shù)組中一開始所有元素均為0。之后的每一個人都是在這個0的基礎(chǔ)上對區(qū)間進行加p的操作。（ps：這里的差分數(shù)組表示的是每分鐘需要的泡澡水的差分，跟人數(shù)n沒有一點關(guān)系?。┲笾灰谝来伪闅v差分數(shù)組，對差分數(shù)組的前綴和與w作比較，判斷以下輸出即可。
? ? ? ? 這題在差分時有個小坑。就是s的取值可能為0。眾所周知，差分數(shù)組的下標是從1取起的，所以需要將s~t的區(qū)間向后移1個單位即可，保證差分數(shù)組下標為0的元素值一定為0。
#include
using namespace std;
using ll = long long;
const int maxn = 1e6;
ll d[maxn];
int main()
{
int n;
ll w;
int maxt = 0;
cin >> n >> w;
for (int i = 1; i <= n; i++){
int s, t, p; cin >> s >> t >> p;
maxt = max(t, maxt);
d[s + 1] += p;
d[t + 1] -= p;
}
for(int i = 1; i <= maxt; i++){
d[i] += d[i - 1];
if (d[i] > w){
cout << "No";
return 0;
}
}
cout << "Yes";
return 0;
}
柚子快報激活碼778899分享：藍橋杯——泡澡
參考文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
PinShop跨境圖釘購
