Meet in another world, enjoy tasty food!(思维)

传送门:Meet in another world, enjoy tasty food!
题目给的数据范围很大,$n$只有1000的范围,考虑$O(N^2)$的做法,并且由于数值很大,那么可以往除法的角度思考。

  • 对于本题,对于每一个round,先求出哪一个最先出队,然后让其出队,后面的跟上来,这里推荐用vector来存储队列,因为通过vector的erase方法可以将后面的人平移过来,这样可以避免考虑位置的转移。
  • 需要注意的是,对于出队的过程,不能让所有的人都减去最少的那个人的次数乘位置,因为这样会造成不平衡
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int N = 1010;
typedef long long ll;
struct node{
    ll id, value;
};
vector<node> vec;
map<ll, ll> mp;
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        ll x;
        cin >> x;
        vec.push_back({i, x});
    }
    int ans = 0;
    while(1){
        ll minn = 1e18;
        int pos = 0;
        for(int i = 0; i < vec.size(); i ++){
            ll temp = ceil((double)vec[i].value / (i + 1));
            if(minn > temp){
                minn = temp;
            }
		}
        for(int i = 0; i < vec.size(); i ++){
            ++ pos;
        	vec[i].value -= (minn - 1)* pos + i + 1;
        	if(vec[i].value <= 0){
        		mp[++ ans] = vec[i].id;
				vec.erase(vec.begin() + i);		
        		i --; 
			}
		}
		if(vec.size() == 0)
			break;
    }
    for(int i = 1; i <= n; i ++)
    	cout << mp[i] << ' ';
    return 0;
}
上一篇:leetcode 最小栈 简单


下一篇:[考试总结]noip模拟51