AcWing 3161. 图形排版
原题链接
简单
作者:
再给我一次AC的机会
,
2024-03-05 13:19:15
,
所有人可见
,
阅读 41
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<ctime>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100005;
PII pic[N];
int m, n;
int sumHeight(int t)
{
int res = 0;
int restW = m, h = 0;
for (int i = 0; i < n; i++)
{
if (t == i)continue;
if (restW > pic[i].x)
{
h = max(h, pic[i].y);
restW -= pic[i].x;
}
else
{
int hx = ceil(pic[i].y * 1.0 * restW / pic[i].x);
h = max(h, hx);
res += h;
h = 0;
restW = m;
}
}
return res + h;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int res = N * 1000;
cin >> m >> n;
for (int i = 0; i < n; i++)
{
cin >> pic[i].x >> pic[i].y;
}
for (int i = 0; i < n; i++)
{
res = min(res, sumHeight(i));
}
cout << res;
return 0;
}