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
程式碼、除錯測資
附上亂亂的code1
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
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 6 |