TIOJ 1318 - 奥步戰術 Tactic

Link: http://tioj.ck.tp.edu.tw/problems/1318

不錯的思考題,感覺滿有難度的,問人才會。不過測資似乎不太強,用gready假解就能喇到90分~AC。

TOJ上加強測資的版本: http://toj.tfcis.org/oj/pro/282/


題解

每個題目分為 0分->部分部分->AC
例如範測可改為:

0分->部分 部分->AC
3 1
2 4
3 2
3 1
2 3

對於 0分->部分 > 部分->AC 的題目我們稱為高門檻題
對於 0分->部分 <= 部分->AC 的題目我們稱為低門檻題

門檻 0分->部分 部分->AC
3 1
3 2
3 1
2 4
2 3

對於全部都是低門檻題的狀況,我們只要把 0分->部分部分->AC 拆開,直接由時間少的開始取即可。
對於全部都是高門檻題的狀況,有一個性質是至多只有一題會拿部分分數。

至於有同時有高門檻題和低門檻題的情形呢? 我們可以枚舉要拿幾個高門檻題,剩下的時間留給低門檻題(二分搜低門檻題可用幾題)

接下來我們遇到了另一個難題,要怎麼快速的枚舉如何拿高門檻題呢? 以下解決方式是自己想+和同學討論的,簡單敘述一下。
可以對高門檻題依據0分->AC的時間做排序,由小的開始拿,至於哪一題要拿部分分數,則從剩下未取的中選一個0分->部分時間最少的,或者從已拿取的中,選一個部分->AC時間最大的改為只拿部分分數。
這作法可透過暴力枚舉觀察一下來證明,不過懶得寫了XD


程式碼、除錯測資

附上亂亂的code

AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii; //first: partial->AC, second: 0->partial
vector<pii> high; //高門檻題
vector<int> low; //低門檻題
int lowp[200010];
bool cmp(pii a,pii b)
{
return a.first+a.second<b.first+b.second;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,t;
cin>>n>>t;
int hc=0,lc=0;
for(int i=0;i<n;i++)
{
int h,c;
cin>>h>>c;
h-=c;
if(h<c)
{
high.push_back({h,c});
hc++;
}
else
{
low.push_back(h);
low.push_back(c);
lc+=2;
}
}
sort(low.begin(),low.end());
sort(high.begin(),high.end(),cmp);
lowp[0]=0;
for(int i=1;i<=lc;i++)
lowp[i]=lowp[i-1]+low[i-1];
int st=0;
for(int i=0;i<hc;i++)
st+=high[i].first+high[i].second;
int ans=0,mnc=1000000000;
multiset<int> mxc;
mxc.insert(0);
for(int i=0;i<hc;i++)
mxc.insert(high[i].first);
for(int i=hc-1;i>=-1;i--)
{
auto solv=[t,&ans,lc](int st,int ic)
{
if(st<=t)
{
int tc=upper_bound(lowp,lowp+lc+1,t-st)-lowp-1;
ans=max(ans,ic+tc);
}
};
solv(st,(i+1)*2);
solv(st+mnc,(i+1)*2+1);
solv(st-*mxc.rbegin(),(i+1)*2-1);
if(i>=0)
{
st-=high[i].first+high[i].second;
mnc=min(mnc,high[i].second);
mxc.erase(mxc.find(high[i].first));
}
}
cout<<ans<<endl;
}

附贈幾筆很強的測資 (可能比官方測資強)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2 6
4 1
5 3
2 5
10 2
5 4
2 6
6 1
9 6
2 11
6 4
7 6
3 23
8 7
11 9
12 8